정렬

정렬이란 2개 이상의 자료를 특정 기준에 의해 작은 값부터 큰 값 순서(오름차순) 또는 그 반대의 순서로(내림차순) 재배열 하는 것을 말한다. 제한이 있는 경우 또는 특수한 경우가 아니면 quick sort(Arrays.sort /Collection.sort)를 활용해 정렬하자. -> 괜히 복잡도 늘리지 않기

 

정렬에서의 키: 자료를 정렬하는 기준이 되는 특정 값

 

정렬의 종류

1. 버블 정렬 -> 버블정렬 시간 복잡도 O(n^2)

2. 선택 정렬 -> 선택정렬 시간 복잡도 O(n^2)

3. 삽입 정렬 -> 삽입정렬 시간 복잡도 O(n^2)

4. 카운팅 정렬 -> 카운팅 정렬 시간 복잡도 O(n+k)

5. 병합 정렬 -> 병합 정렬 시간 복잡도 O(nlogn)

6. 퀵 정렬 -> 퀵 정렬 시간 복잡도 O(n^2 ) -> 평균적인 경우 O(nlogn)

→ 상위 3개와 같은 효율적이지 않은 정렬를 배워야 하는 이유: 세부 기술 응용 가능하기 때문

 

1. 버블 정렬 (비교와 교환)

인접한 두개의 원소를 비교하며 자리를 계속 교환하는 방식으로 내가 주로 이용하는 방식이다. 이중 반복문을 활용하여 구현하기 때문에 시간 복잡도는 O(n^2)이다. 한 단계가 끝나면 가장 큰 원소가 마지막 자리로 정렬된다. 그렇게 수만큼 반복해서 정렬한다. 버블 정렬은 가장 뒤에서부터 정렬 선택정렬은 가장 앞부터 정렬된다. 

 

2. 선택 정렬 (비교와 교환; 교환의 횟수=버블)

저장되어 있는 자료에서 k번째로 큰 또는 작은 원소를 찾는 방법을 말한다. (k값이 작을 때 유용)-> 최소값, 최대값, 중앙값 찾는 알고리즘 

예시. 당구대 위에 있는 공 중 가장 작은 숫자의 공부터 골라서 차례대로 정리하는 것.

주어진 배열에서 최소값을 반복문을 통해 찾고 원소를 순회하면서 최소값과 비교해 더 작은 경우 배열의 첫 원소로 이동시키고 그 원소를 제외하고 나머지 원소들을 대상으로 과정을 반복해 정렬한다. 버블 정렬은 가장 뒤에서부터 정렬 선택정렬은 가장 앞부터 정렬된다. 

선택과정은 정렬 알고리즘을 이용해 정렬하고 원하는 순서에 있는 원소를 가져오는 것이다.

 

3. 카운팅 배열(비교환방식)

 

항목들의 순서를 결정하기 위해 집합에 각 항목의 빈도를 새로운 배열로 만들어 세는 작업을 수행한다. 

제한사항: 정수나 정수로 표현할 수 있는 자료에 대해서만 적용 가능 -> 각 항목의 발생 횟수를 기록하기 위해 정수 항목으로 인덱스 되는 카운트들의 배열을 사용하기 때문. 카운트를 위한 충분한 공간을 할당하려면 집합 내 가장 큰 정수를 알아야 한다.

정렬된 집합에서 각 항목의 앞에 위치할 항목의 개수를 반영하기 위해 counts의 원소를 조정하는데 단순히 인덱스에 해당하는 값을 들쭉 날쭉하게 원소 값으로 두는 것이 아닌 각 원소 단계에서 누적합을 만들어줘야 한다. → 직전 값을 자기 자신에게 더해줘야 하는데 → 속도가 빠르도록

 

<카운팅 배열을 이용한 정렬 구현>

package test02;

import java.util.Arrays;

public class practice_self {
	public static void main(String[] args) {

		// 배열 생성
		int[] arr = { 2, 4, 0, 1, 1, 3, 5, 7, 6, 5 };
		int max = -1;
		for (int i = 0; i < arr.length; i++) {
			if (max < arr[i]) {
				max = arr[i];
			}
		}

		System.out.println(max);
		System.out.println(Arrays.toString(arr));

		// 카운팅 배열 생성
		int[] cnt = new int[max + 1];
		for (int i = 0; i < arr.length; i++) {
			cnt[arr[i]] += 1;
		}

		System.out.println(Arrays.toString(cnt));

		// 누적합 배열 생성

		int[] add = new int[max + 1];
		add[0] = cnt[0];
		for (int i = 1; i < add.length; i++) {
			add[i] = cnt[i] + add[i - 1];
		}
		System.out.println(Arrays.toString(add));

		// 정렬한 값을 넣을 배열 생성

		int[] arr2 = new int[arr.length];

		for (int i = 0; i < arr2.length; i++) {
			arr2[add[arr[i]]-1] = arr[i];
			add[arr[i]]--;
		}
		System.out.println(Arrays.toString(arr2));
	}
}

 

카운팅 정렬을 항상 사용하는 게 좋은가? → 큰 수가 배열에 포함되어 있을 때 오히려 메모리 낭비가 발생한다.

카운팅 정렬 == 안정정렬 → 똑같은 값을 가지는 복수의 원소들이 정렬 후에도 정렬 전과 같은 순서를 가진다는 의미(단, 누적합 배열에서 정렬배열로 적용 시 원래 배열의 가장 마지막 원소부터 수행해야 함)