[java] 기본 정렬 알고리즘

swap 알고리즘

 

	public static void swap(int[] arr, int idx1, int idx2) {
		int temp = arr[idx1];
		arr[idx1]= arr[idx2];
		arr[idx2] = temp;
	}

 

 

 

버블정렬

public static void BubbleSort(int[] arr) {
		for(int i=0; i<arr.length-1; i++) {
			for(int j=0; j<arr.length-1-i; j++) {
				if(arr[j]>arr[j+1]) {
					swap(arr,j,j+1);
				}
			}
		}
	}

n^

 

 

선택정렬

맨 앞 인덱스부터 차례대로 들어갈 원소를 선택하여 정렬

인덱스 0~ n-1 을 돌면서 원소의 값이 가장 작은 인덱스를 찾는다.

인덱스 0과 가장 작은 인덱스 원소 swap

1~n-1에서 가장 작은 원소 찾기 -> swap

	public static void SelectSort(int[] arr) {
		for(int i=0; i<arr.length-1; i++) {
			int min = i; 
			for(int j=i+1; j<arr.length; j++) {
				if(arr[min]>arr[j]) {
					min =j;
				}
			}
			swap(arr,i,min);
		}
	}

 

 

삽입정렬

인덱스 1의 원소부터 앞 방향으로 들어갈 위치를 찾아 교환하는 정렬 알고리즘

인덱스 1 ~ n-1 의 원소들을 순차적으로 자신이 들어갈 위치에 넣는다.

while문을 사용하여 더 작으면 계속 앞으로 전진시키면서 비교한 원소를 한 칸씩 뒤로 민다.

들어갈 자리가 정해지면 넣어준다.

시간복잡도 worst: O(n^2) average: O(n^2), best:O(n)

public static void InsertSort(int[] arr) {
		for(int i=1; i<arr.length; i++) {
			int temp = arr[i];
			int j = i-1;
			while(j>=0 && temp<arr[j]) {
				arr[j+1] = arr[j];
				j--;
			}
			arr[j+1] =temp;
		}
	}

 

합병정렬 

mergeSort()는 반으로 나누면서 재귀호출

다 나눠졌으면 올라가면서 merge()

merge()는 두 부분 배열의 인덱스를 점차적으로 비교하면서 정렬

시간복잡도 O(nlog n) 최악,평균,최고

 

 

퀵정렬

피봇을 사용한 정렬 알고리즘, 분할 정복 알고리즘

worst O(n^2) , average: O(nlogn), best:O(nlogn)

public static void sortByQuicksort(int[] arr) {
		quickSort(arr,0,arr.length-1);
	}
	
	public static void quickSort(int[] arr,int left, int right) {
	
		int part = partition(arr,left,right);
		if(left<part-1) {
			quickSort(arr,left,part-1);
		}
		if(part<right) {
			quickSort(arr,part,right);
		}
		
	}
	
	
	public static int partition(int[] arr, int left, int right) {
		int pivot = arr[(left+right)/2];
		
		while(left<=right) {
			while(arr[left]<pivot) {
				left++;
			}
			while(arr[right]>pivot) {
				right--; // 피봇보다 작은값을 만날때까지 움직임
			}
			
			if(left<=right) {
				swap(arr,left,right);
				left++;
				right--;
			}
		}
		
		
		return left;
	}

 

힙정렬

 

 

참조

https://velog.io/@pppp0722/%EC%A0%95%EB%A0%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-7%EA%B0%9C-%EC%A0%95%EB%A6%AC-Java

 

https://ardor-dev.tistory.com/53