1. 선택정렬

selectionsort

  • 각 루프마다
    • 최대 원소를 찾는다
    • 최대 원소와 맨 오른쪽 원소를 교환한다.
    • 맨 오른쪽 원소를 제외한다.
  • 하나의 원소만 남을때까지 루프를 반복

  • 시간복잡도 : T(n) = (n-1) + (n-2) + … + 2 + 1 = O(n2)
    • 최악, 평균, 최선의 경우에도 n(n-1)/2 번의 연산을 수행하므로 O(n2) 이다.
package study;

import java.util.Arrays;

public class SelectionSort {
	public static void main(String[] args) {
		int[] arr = {3,5,4,8,6,1,7,9,2};
		System.out.println("정렬 전 : " + Arrays.toString(arr));
		SelectionSort sort = new SelectionSort();
		sort.selectSortMin(arr);
		System.out.println("정렬 후 : " + Arrays.toString(arr));
	}
	
	public void selectSortMin(int[] arr) {
		int min;
		int tmp;
		for (int i = 0; i < arr.length; i++) {
			min = i;
			for (int j = i+1; j < arr.length; j++) {
				if(arr[min] > arr[j]) {
					min = j;
				}
			}
			tmp = arr[i];
			arr[i] = arr[min];
			arr[min] = tmp;
		}
	}
	
	public void selectSortMax(int[] arr) {
		int max;
		int tmp;
		for (int i = arr.length-1; i > 0; i--) {
			max = i;
			for (int j = i-1; j >= 0; j--) {
				if(arr[max] < arr[j]) {
					max = j;
				}
			}
			tmp = arr[i];
			arr[i] = arr[max];
			arr[max] = tmp;
		}
	}
	
}

2. 버블정렬

bubblesort

  • 각 루프마다
    • 연속된 두개 원소를 비교한 후 큰 값을 뒤로 넘긴다.(오름차순 기준)
    • 마지막 번째에 도착한 원소가 가장 큰값이 된다.
    • 맨 오른쪽(마지막 번째) 원소를 제외한다.
  • 하나의 원소만 남을때까지 루프를 반복
  • 시간복잡도 : T(n) = (n-1) + (n-2) + … + 2 + 1 = O(n2)
    • 최악, 평균, 최선의 경우에도 n(n-1)/2 번의 연산을 수행하므로 O(n2) 이다.
package study;

import java.util.Arrays;

public class BubbleSort {
	public static void main(String[] args) {
		int[] arr = {3,5,4,8,6,1,7,9,2};
		System.out.println("정렬 전 : " + Arrays.toString(arr));
		BubbleSort bs = new BubbleSort();
		bs.bubbleSort(arr);
		System.out.println("정렬 후 : " + Arrays.toString(arr));
	}
	
	public void bubbleSort(int[] arr) {
		for (int i = arr.length-1; i > 0; i--) {
			for (int j = 0; j < i; j++) {
				if(arr[j] > arr[j+1]) {
					int tmp = arr[j+1];
					arr[j+1] = arr[j];
					arr[j] = tmp;
				}
			}
		}
	}
}

삽입정렬

insertionsort

  • 맨 처음 원소는 정렬된 상태로 본다.
  • 각 루프마다
    • 자신의 앞 원소들을 비교하면서 자신이 들어가야 할 자리를 찾아 들어간다
    • 본인의 자리를 찾았다면 그 사이에 값을 넣기 위해, 기존의 원소들을 한칸씩 옮겨야 한다.
    • 이러한 번거러움을 줄이기 위해 뒤에서부터 탐색하는 방향으로 한다.
  • 시간복잡도 : T(n) = (n-1) + (n-2) + … + 2 + 1 = O(n2)
    • 최선의 경우는 O(n) 의 연산을 가진다.
package study;

import java.util.Arrays;

public class InsertionSort {
	public static void main(String[] args) {
		int[] arr = {3,5,4,8,6,1,7,9,2};
		System.out.println("정렬 전 : " + Arrays.toString(arr));
		InsertionSort is = new InsertionSort();
		is.insertionSort(arr);
		System.out.println("정렬 후 : " + Arrays.toString(arr));
	}
	
	public void insertionSort(int[] arr) {
		for (int i = 1; i < arr.length; i++) {
			for (int j = i; j > 0; j--) {
				if(arr[j-1] > arr[j]) {
					int tmp = arr[j-1];
					arr[j-1] = arr[j];
					arr[j] = tmp;
				}
			}
		}
	}
}

마치며

  • 평소에 코딩테스트 문제를 풀때에 아무런 고민 없이 자바에서 제공하는 라이브러리(Arrays.sort())를 이용하여 정렬을 했었다. 그 라이브러리는 어떤 정렬 알고리즘으로 구현이 됐는지 전혀 모른채… (알아보니 이중 퀵 소트 라던데, 다음에 이 정렬에 대해 알아보는 포스트를 작성 해야겠다.)

  • 그리하여 오늘은 기본적인 정렬 알고리즘에 대해서 공부해보았다. 각각의 정렬 알고리즘은 어떻게 동작하는지 알아보고, 코드로 직접 구현해보는 것(막상 직접 손으로 구현하라고 했을때 시간이 꽤 걸렸다ㅠ)이 중요한 것 같다. 특히 삽입정렬은 원소를 특정위치에 집어 넣을때 기존 원소들을 한칸씩 뒤로 미루는 작업을 해야하는것.