[JAVA] <Sort 알고리즘 정리>

어제부터 Sort를 이용하는 Programmers 연습 문제를 풀기 시작했는데, 어제 푼 문제가 LV1이여서 그런건지, 아니면 내가 java에 내장되어있는 sort()를 사용해서 그런건지 모르겠는데 역대급 낮은 점수인 2점을 받았다... 

그렇게 심각한 문제는 아니지만, 혹시 sort 알고리즘을 내부에서 직접 구현을 안해서 그런거라면..? 하는 생각이 들어서

더 높은 LV의 sort문제를 풀기 전에 한번 정리를 하고 넘어가려고 한다. (Heap Sort는 이전 포스팅에서 한번 다뤘으니 따로 다루지는 않겠다.)

 

1. Bubble Sort

 인접한 두 인자가 정해진 순서를 따르고 있지 않다면, 두 인자의 위치를 바꾸며 정렬을 진행하는 정렬 방법이다.

즉,

• 4 2 1 5 3
• 2 4 1 5 3
• 2 1 4 5 3
• 2 1 4 5 3
• 2 1 4 3 5

이런 식으로 정렬이 진행되는 Sort이다. 

public static void bubbleSort(int[] a) { 
		boolean sorted = false;
		int temp;
		while (!sorted) {
			sorted = true;
			for (int i = 0; i < a.length - 1; i++) {
				if (a[i] > a[i + 1]) { // 바로 뒤에 있는 인자가 앞에 인자보다 작다면
					temp = a[i];
					a[i] = a[i + 1];
					a[i + 1] = temp;
					sorted = false;
				}
			}
		}
	}

 

---

2. Insertion Sort

배열을 정렬이 이미 되어있는 부분(sorted)과 아닌 부분(unsorted)으로 나누고, unsorted의 인자들을 하나 씩 sorted에 삽입하는 방식

• 3 5 7 8 4 2 1 9 6
• 3 5 7 x 8 2 1 9 6
• 3 5 x 7 8 2 1 9 6
• 3 x 5 7 8 2 1 9 6
• 3 4 5 7 8 2 1 9 6

	public static void insertionSort(int[] a) { // 배열을 정렬이 이미 되어있는 부분(sorted)과 아닌 부분(unsorted)으로 나누고, unsorted의 인자들을 하나씩
												// sorted에 삽입하는 방식

		for (int i = 1; i < a.length; i++) {
			int current = a[i];
			int j = i - 1;
			while (j >= 0 && current < a[j]) { // j가 -1이 되거나 정렬이 될 때까지 비교 후 삽입 위치를 정한다.
				a[j + 1] = a[j];
				j--;
			}
			a[j + 1] = current; // 정렬이 된 순간의 위치에 current를 삽입
		}
	}

---

3. Selection Sort

마찬가지로 배열을 sorted와 unsorted로 나누지만, sorted 배열의 마지막 인자와 unsorted배열의 최소값을 찾아 교환하는 방식이다.

• 3 5 1 2 4
• 1 5 3 2 4
• 1 2 3 5 4
• 1 2 3 5 4
• 1 2 3 4 5
• 1 2 3 4 5

	public static void selectionSort(int[] a) {
		for (int i = 0; i < a.length; i++) {
			int min = a[i];
			int minId = i;
			for (int j = i + 1; j < a.length; j++) {
				if (a[j] < min) {
					min = a[j];
					minId = j;
				}
			}
			// swapping
			int temp = a[i];
			a[i] = min;
			a[minId] = temp;
		}
	}
	

---

4. Merge Sort

mid를 기준으로 반을 나누어  정렬, 정렬이 다 끝날 때까지 recursion하는 방식이다.

//mid를 기준으로 반을 나누어  정렬, 정렬이 다 끝날 때까지 recursion
	public static void mergeSort(int[] array, int left, int right) {
	    if (right <= left) return;
	    int mid = (left+right)/2;
	    mergeSort(array, left, mid);
	    mergeSort(array, mid+1, right);
	    merge(array, left, mid, right);
	}
	
	public static void merge(int[] array, int left, int right, int mid) {

		int lengthLeft = mid - left + 1;
		int lengthRight = right - mid;

		int leftArray[] = new int[lengthLeft];
		int rightArray[] = new int[lengthRight];

		for (int i = 0; i < lengthLeft; i++)
			leftArray[i] = array[left + i];
		for (int i = 0; i < lengthRight; i++)
			rightArray[i] = array[mid + i + 1];

		int leftIndex = 0;
		int rightIndex = 0;

		for (int i = left; i < right + 1; i++) {
			if (leftIndex < lengthLeft && rightIndex < lengthRight) {
				if (leftArray[leftIndex] < rightArray[rightIndex]) {
					array[i] = leftArray[leftIndex];
					leftIndex++;
				} else {
					array[i] = rightArray[rightIndex];
					rightIndex++;
				}
			}
			else if (leftIndex < lengthLeft) {
				array[i] = leftArray[leftIndex];
				leftIndex++;
			}

			else if (rightIndex < lengthRight) {
				array[i] = rightArray[rightIndex];
				rightIndex++;
			}
		}
	}

---

5. Shell Sort

간격(보통은 size/2)사이에 있는 두 인자를 비교하여 sort, 한 사이클 진행 후 간격을 /2 한다.

	public static void intervalSort(int a[], int begin, int end, int interval) {
		int j;
		for(int i = begin+interval; i <= end; i=i+interval) {
			int item = a[i];
			for(j = i - interval; j >= begin && item<a[j]; j = j-interval) {
				a[j + interval] = a[j];
			}
			a[j + interval] = item;
		}
	}
	
	public static void shellSort(int[] a, int size) {
		int interval = size/2;
		while(interval >= 1) {
			for(int i =0; i < interval; i++) {
				intervalSort(a, i, size-1, interval);
			}
			interval /= 2;
		}
	}
	

---

6. Quick Sort

기준 값을 정해서 기준 값과 값을 비교 후 정렬하는 방식, JAVA의 Collection Class에 있는 sort()가 이 방식이다.

출처: https://www.youtube.com/watch?v=cnzIChso3cc

public static int[] quickSort(int[] a, int l, int r) {
		 int p = partition(a, l, r);
		 if(l<p-1) {
			 quickSort(a, l, p-1);
		 } 
		 if(p < r) {
			 quickSort(a, p, r);
		 }
		 return a;
	 }
	 
	 public static int partition(int[] a, int l, int r) {
		 int privot = a[(l+r)/2];
		 while(l<=r){
			 while(a[l] < privot) l++;
			 while(a[r]>privot) r--;
			 if(l<=r) {
				 int temp = a[l];
				 a[l] = a[r];
				 a[r] = temp;
				 l++;
				 r--;
			 }
		 }
		 return l;
	 }