[정렬] 개념정리1 - 삽입 정렬, 선택 정렬, 퀵 정렬, 계수 정렬

개념

→ 정렬 : 데이터를 특정한 기준에 따라 오름차순 or 내림차순으로 나열하는 것

→ 자료 탐색에 있어서 필수적임!

 

→ 정렬 알고리즘으로 데이터를 정렬하면 이진 탐색이 가능해짐(정렬은 이진 탐색의 전처리 과정이기도 함)

추가) 오름차순으로 정렬된 데이터들을 내림차순 정렬할 경우 : 리스트 뒤집는 연산은 O(N)의 복잡도로 간단히 수행 가능함

---

분류

*정렬 알고리즘 선택 기준

→ 모든 경우에 최적인 정렬 알고리즘은 없음

→ 각 응용분야에 적합한 정렬 방법을 사용해야 함

ex) 레코드 수의 많고 적음, 레코드 크기의 크고 작음, key의 특성(문자, 정수, 실수 등), 메모리 내부/외부 정렬

 

*정렬 알고리즘의 평가 기준

→ 비교 횟수의 많고 적음, 이동 횟수의 많고 적음

 

*정렬 알고리즘 분류 

[1] 

단순하지만 비효율적 : 선택 정렬, 삽입 정렬, 버블 정렬

복잡하지만 효율적 : 쉘 정렬, 퀵 정렬, 히프 정렬, 기수 정렬

[2]

내부 정렬(internal sorting) : 모든 데이터가 주기억장치에 저장된 상태에서 정렬됨

외부 정렬(external sorting) : 외부 기억장치에 대부분의 데이터가 있고, 일부만 주기억장치에 저장된 상태에서 정렬 

---

정렬 알고리즘의 안정성(stability)

→ 동일한 키 값을 갖는 레코드들의 상대적인 위치가 정렬 후에도 바뀌지 않음

 

안정하지 않은 정렬의 예시

---

정렬 알고리즘

1. 선택 정렬

 

선택 정렬

→ 아이디어 : 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복함 

→ 매번 '가장 작은 것을 선택'한다는 의미에서 선택 정렬 알고리즘이라고 함

→ 가장 작은 데이터를 앞으로 보내는 과정을 N-1 번 반복하면 정렬 완료됨 

 

[코드]

public class selectionSortEx1 {

	public static void main(String[] args) {
		
		int[] arr = {5,6,3,4,1,2,7,8,9,0};
		
		for(int i = 0; i < arr.length; i++) {
			int minValIndex = i; //가장 작은 원소의 인덱스 
			for(int j = i + 1; j < arr.length; j++) { //반복문 연산횟수 : N, N-1, N-2 . . .
				if(arr[j] < arr[minValIndex])
					minValIndex = j; 
			}
			
			//swap
			int temp = arr[i];
			arr[i] = arr[minValIndex];
			arr[minValIndex] = temp;
		}
		
		for(int i = 0; i < arr.length; i++)
			System.out.print(arr[i] + " ");
	}
}

→ SWAP : 특정한 리스트가 주어졌을 때 두 변수의 위치를 변경하는 작업

 

[시간 복잡도]

→ 선택 정렬은 N-1번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 함

→ 위의 코드를 보면, 2중 for문이 연산 횟수에 가장 큰 영향을 미침 

    연산 횟수 : N + (N-1) + (N-2) + . . . + 2 → 근사치 : (N^2 + N)/2 → 빅오 표기법 : O(N^2)

→ 다른 정렬 알고리즘에 비해 효율적이지 않음, BUT! 특정한 리스트에서 가장 작은 데이터를 찾는 경우에 사용할 수 있으므로 기억해두기!

 

2. 삽입 정렬

 

 

삽입 정렬

→ 선택 정렬에 비해 실행 시간 측면에서 더 효율적인 알고리즘 

 

→ 특히 필요할 때에만 위치를 바꾸므로 '데이터가 거의 정렬되어 있을 때' 효율적임

 

→ 특정한 데이터를 적절한 위치에 삽입한다는 것의 의미 :

        특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정함

        정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤 해당 위치에 삽입된다는 특징

        → 즉 2번째 데이터부터 시작함(1번째 데이터는 그 자체로 정렬되어 있다고 가정)

 

→ 적절한 위치에 삽입하는 과정을 N-1 번 반복하면 정렬 완료됨 

 

[코드]

public class insertionSortEx1 {

	public static void main(String[] args) {
		
		int[] arr = {3,5,2,1,6,7,4,8,9,0};
		
		for(int i = 1; i < arr.length; i++) { //배열의 2번째 원소부터 
			for(int j = i; j > 0; j--) { //j : 정렬되어지고 있는 해당 원소의 위치 
				if(arr[j] < arr[j-1]) {
					int temp = arr[j];
					arr[j] = arr[j-1];
					arr[j-1] = temp;
				}
				else break; //자기보다 작은 데이터를 만나면 해당 위치에서 멈춤 
			}
			
		}
		
		for(int i = 0; i < arr.length; i++)
			System.out.print(arr[i] + " ");
	}
}

 

[시간 복잡도]

→ 2중 for문이 가장 큰 영향을 미침

    최악의 경우(내림차순 정렬되어 있는 경우) 연산 횟수 : 1 + 2 + ... + N-1 → 빅오 표기법 : O(N^2)

 

→ 하지만, 삽입 정렬은 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작함! 

    최선의 경우(오름차순 정렬되어 있는 경우) : 1 + 1 + ... + 1 → 빅오 표기법 : O(N)

→ 퀵 정렬과 비교했을 때 정렬이 거의 되어 있는 경우에는 삽입 정렬이 더 빠름

→ 즉, 만약 거의 정렬되어 있는 상태로 입력이 주어진다면, 삽입 정렬을 사용하는 것이 효과적임 

 

3. 퀵 정렬 

→ 정렬 알고리즘 중 가장 많이 사용되는 알고리즘

→ 분할정복법(divde and conquer) 사용

 

추가) 

퀵 정렬과 비교할 만큼 빠른 알고리즘으로 '병합 정렬' 알고리즘이 있음   

퀵 정렬 & 병합 정렬은 대부분의 프로그래밍 언어에서 정렬 라이브러리의 근간이 되는 알고리즘임

 

과정)

    리스트를 2개의 부분리스트로 비균등 분할하고, 각각의 부분리스트를 다시 quick sort(재귀호출)

    피벗을 설정한 뒤 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾음 -> 큰 데이터와 작은 데이터의 위치 교환 -> 해당 과정을 반복하면 피벗에 대하여 정렬이 수행됨 

→ 피벗(pivot) : 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 기준 

→ 퀵 정렬 수행 전 피벗을 어떻게 설정할 것인지 미리 명시해야 함

→ 가장 대표적인 분할 방식은 호어 분할(Hoare Partition)

    호어 분할에서 피벗 설정 방식 : 리스트에서 첫 번째 데이터를 피벗으로 정함

 

[코드]

import java.util.*;

public class QuickSort{

  public static void quickSort(int[] arr, int start, int end){
    if(start >= end) return; //재귀 종료 조건 - 원소가 1개인 경우 

    int pivot = start; //피벗은 첫 번째 원소로 설정
    int left = start + 1;
    int right = end;
    
    while(left <= right){
      // left - 피벗보다 큰 값을 찾을 때까지 반복  
      while(left <= end && arr[left] <= arr[pivot]) left++;
      // right - 피벗보다 작은 값을 찾을 때까지 반복 
      while(right > start && arr[right] >= arr[pivot]) right --;
      
      if(left > right){ //left와 right보다 앞섰을 때 
        int temp = arr[pivot];
        arr[pivot] = arr[right];
        arr[right] = temp;
      }
      else{
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp; 
      }
    }
    //정렬된 값 기준으로 분할된 왼쪽과 오른쪽 부분에 대해 각각 정렬 수행 - 재귀호출
    quickSort(arr, start, right - 1);
    quickSort(arr, right + 1, end);
  }

  public static void main(String[] args){
    int n = 10;
    int[] arr = {4, 6, 7, 5, 1, 3, 2, 8, 9, 0};

    quickSort(arr, 0, n - 1);

    for(int i = 0; i < n; i++)
      System.out.print(arr[i] + " ");
  } 

}

 

[시간복잡도]

평균 시간 복잡도 : O(NlogN) 

최선의 경우 :

      피벗값의 위치가 변경되어 분할이 일어날 때마다 왼쪽과 오른쪽을 절반씩 분할하는 경우 

최악의 경우 : O(N^2) → 이미 데이터가 정렬되어 있는 경우에는 느리게 동작함 

 

4. 계수 정렬 (Counting Sort) 

 

→ 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘 

 

→ 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용 가능함

ex) 데이터의 값이 무한의 범위를 가질 수 있는 실수형 데이터는 사용하기 어려움

→ 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용 가능함 

    이유) 계수 정렬 사용 시 '모든 범위를 담을 수 있는 크기의 리스트를 선언'해야 하기 때문임  

 

과정

(가장 큰 데이터 - 가장 작은 데이터) + 1 크기의 배열 선언정렬 대상이 되는 숫자들에 해당하는 인덱스의 값 1씩 증가 첫 번째 인덱스부터 해당 인덱스의 값만큼 숫자 출력 정렬 완료! 

 

[코드]

import java.util.*;

public class Main {

  public static final int MAX_VALUE = 9; // 주어진 데이터 중 최대값 

  public static void main(String[] args){

    int n = 15;
    int[] arr = {7,5,4,3,2,1,6,9,8,6,4,5,3,2,0};

    // 주어진 수의 모든 범위를 포함하는 배열 선언 (모든 값은 0으로 초기화)
    int[] count = new int[MAX_VALUE + 1];

    for(int i = 0; i < n; i++){ // N 
      count[arr[i]]++; //각 데이터에 해당하는 인덱스의 값 증가  
    }

    for(int i = 0; i <= MAX_VALUE; i++){ // K
      for(int j = 0; j < count[i]; j++)
        System.out.print(i + " ");
    }
  }

}

[시간 복잡도]

모든 데이터가 양의 정수인 상황에서 주어진 데이터의 개수가 N, 데이터 중 최대값의 크기를 K라고 할 때 : O(N + K)

→ 데이터의 범위가 한정되어 있다면 효과적으로 사용 가능하고 항상 빠르게 동작함 

 

[공간 복잡도]

But 계수 정렬은 때에 따라서 심각한 비효율성을 초래할 수 있음 ex) 데이터가 0과 999,999 단 2개만 존재하는 경우에도 리스트의 크기가 100만 개가 되도록 선언해야 함: O(N + K)

 

적용 상황

따라서 항상 사용할 수 있는 정렬 알고리즘은 아니고, 동일한  값을 가지는 데이터가 여러 개 등장할 때 적합함  데이터의 특성을 파악하기 어렵다면 퀵 정렬을 이용하는 것이 유리함데이터의 크기가 한정되어 있고, 데이터가 많이 중복되어 있을수록 유리함

---

추가

코딩 테스트에서의 정렬 문제

 정렬 알고리즘은 정립되어 있기 때문에 정렬 알고리즘 문제는 어느 정도 정해진 답이 있는 문제라고 할 수 있음 직접 정렬 알고리즘을 작성하게 되는 경우도 있지만 미리 만들어진 라이브러리를 이용하는 것이 효과적임 

 

*코딩 테스트에서 정렬 알고리즘이 사용되는 3가지 유형

1. 정렬 라이브러리로 풀 수 있는 문제

→ 단순히 정렬 기법을 알고 있는지 물어보는 문제로 기본 정렬 라이브러리의 사용 방법을 숙지하고 있어야 함 

 

2. 정렬 알고리즘의 원리에 대해서 물어보는 문제

→ 선택, 삽입, 퀵 정렬 등의 원리를 알고 있어야 함 

 

3. 더 빠른 정렬이 필요한 문제 

→ 퀵 정렬 기반의 정렬 기법으로는 풀 수 없으며 계수 정렬(Counting Sort) 등의 다른 정렬 알고리즘을 이용하거나 문제에서 기존에 알려진 알고리즘의 구조적인 개선을 거쳐야 함

 

정렬 라이브러리의 시간 복잡도

정렬 라이브러리는 항상 최악의 경우에도 시간 복잡도 O(NlogN)을 보장함 

 

참고) '이것이 취업을 위한 코딩테스트다' 책