Solving Skill ] 정렬

정렬(Sorting)

"데이터를 특정 기준에 따라 순서대로 나열하는 알고리즘"

 

V 이진 탐색의 전처리 과정이기도 합니다.

 

V 다양한 정렬 알고리즘의 시간 복잡도

출처 : d2

 

---

 

🍎 선택 정렬

"가장 작은 것을 선택"하는 알고리즘

 

⏱ 시간 복잡도

     :  Θ(n^2)

 

 

V 정렬 방법

1. 주어진 리스트 중에 최소값을 찾는다.

2. 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).

3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

V 예시

	테이블	최솟값
0	[9,1,6,8,4,3,2,0]	0
1	[0,1,6,8,4,3,2,9]	1
2	[0,1,6,8,4,3,2,9]	2
3	[0,1,2,8,4,3,6,9]	3
4	[0,1,2,3,4,8,6,9]	4
5	[0,1,2,3,4,8,6,9]	6
6	[0,1,2,3,4,6,8,9]	8

V  예시 코드( C )

void selectionSort(int *list, const int n)
{
    int i, j, indexMin, temp;

    for (i = 0; i < n - 1; i++)
    {
        indexMin = i;
        for (j = i + 1; j < n; j++)
        {
            if (list[j] < list[indexMin])
            {
                indexMin = j;
            }
        }
        temp = list[indexMin];
        list[indexMin] = list[i];
        list[i] = temp;
    }
}

 

 

---

🍎 삽입 정렬

"특정한 데이터를 적절한 위치에 삽입"하는 알고리즘

 

V 필요할 때만 위치를 변경합니다. 따라서 '거의 정렬된 상태일 때 효율적인 알고리즘'입니다.

⏱ 시간 복잡도

     :  Θ(n^2)   

        ** 주어진 배열이 거의 정렬이 되어있다면 가장 빠르게 정렬할 수 있다.

 

 

V  예시 코드( C++ )

#include <iostream>
using namespace std;

int main() {
	int arr[] = {5, 4, 9, 6, 1, 3, 2, 8, 7};
	int temp = 0;
	
	// 두 번째 원소부터 sorting
	for(int i = 1; i < 9; ++i){
		int temp = 0;
		for(int j = i; j > 0; --j){
			if(arr[j] < arr[j - 1]){
				temp = arr[j];
				arr[j] = arr[j - 1];
				arr[j - 1] = temp;
			}else break;
		}
	}
	
	for(int i = 0; i < 9; ++i) cout << arr[i] << ' ';
	
	return 0;
}

 

 

---

🍎 퀵 정렬

"기준을 설정한 뒤, 큰 수와 작은 수를 교환한 후에 배열을 반으로 나누는" 알고리즘

 

V 매 단계에서 적어도 1개의 원소가 자기 자리를 찾게 되므로 이후 정렬할 개수가 줄어듭니다.

V 일반적인 경우 퀵 정렬은 다른 O(n log n) 알고리즘에 비해 훨씬 빠르게 동작합니다.

분할 -> 왼쪽 sort -> 오른쪽 sort

 

 

V 정렬 방법

분할 정복(divide and conquer) 방법을 통해 리스트를 정렬합니다.

1. 리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 *피벗이라고 한다.

2. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.

3. 분할된 두 개의 작은 리스트에 대해 재귀로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다.

 * pivot은 임의의 pivot 값이다. 즉 설정하는 방식에 따라 처음이나 마지막 값 등으로 설정이 가능하다.

 

 

⏱ 시간 복잡도

     :  Θ(n log n)   

 

 

V  예시 코드( C++ )

void swap(int &a, int &b){
    int t = a; a = b; b = t;
}

void quickSort(int A[], int low, int high) {
    if(low >= high) return; // base condition

    // divide process
    int i = low-1, j = low;
    int&pivot = A[high];
    for (; j < high; ++j) {
        if ( A[j] < pivot)
            swap(A[++i], A[j]);
    }
    swap(A[++i], pivot);

    // conquer process
    quickSort(A, low, i-1);
    quickSort(A, i+1, high);
}

 

 

---

🍎 계수 정렬

"크기를 기준으로 각 숫자가 몇번 등장했는지 세어주는" 정렬 알고리즘

 

V 데이터 범위가 정수 형태로 표현될 때

   혹은 가장 큰 데이터와 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적입니다.

 

따라서 위의 count 결과 대로 index를 출력해주면 됩니다.

이해가 안 된다면... 코드를 보면 바로 이해가 되실 겁니다.

 

 

⏱ 시간 복잡도

     :  Θ(n + k)    // k는 정렬할 수들 중에 가장 큰 수 

       ** k가 n보다 매우 큰 수이면 O(무한)이 될 수도 있습니다.

 

 

V  예시 코드( C++ )

#include <bits/stdc++.h>
#define MAX_VALUE 9

using namespace std;

// 출처 : https://github.com/ndb796/python-for-coding-test/blob/master/6/6.cpp

int n = 15;
// 모든 원소의 값이 0보다 크거나 같다고 가정
int arr[15] = {7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2};
// 모든 범위를 포함하는 배열 선언(모든 값은 0으로 초기화)
int cnt[MAX_VALUE + 1];

int main(void) {
    for (int i = 0; i < n; i++) {
        cnt[arr[i]] += 1; // 각 데이터에 해당하는 인덱스의 값 증가
    }
    for (int i = 0; i <= MAX_VALUE; i++) { // 배열에 기록된 정렬 정보 확인
        for (int j = 0; j < cnt[i]; j++) {
            cout << i << ' '; // 띄어쓰기를 기준으로 등장한 횟수만큼 인덱스 출력
        }
    }
}

 

 

 

 

---

 🌷 문제

    이것이 취업을 위한 코딩 테스트다

       유형 1 - 위에서 아래로

       유형 2 - 성적이 낮은 순서로 학생 출력하기

       유형 3 - 두 배열의 원소 교체 

 

    프로그래머스

      정렬 문제 모음

나의 풀이

k번째 수

가장 큰 수

H-Index

 

 

 

---

reference

 

+ NaverD2

   평균 시간 복잡도

 

+ wikipedia

   선택 정렬

   삽입 정렬

   퀵 정렬

   계수 정렬_1

  계수 정렬_2

  계수 정렬_3