[알고리즘 스터디] 정렬(Sorting) 종류들 - 1

정렬(Sort)이란?

 정렬은 말 그대로 특정하게 정한 임의의 순서대로(알파벳 순, 숫자 순)으로 어떠한 배열/리스트를 나열하는 것이다. 정렬은 여러 응용분야에 사용되는 매우 기본적인 문제이다.

오름차순 정렬
[0, 1, ,2, 3, ...]

정렬 종류 

정렬의 종류에는 크게 간단한 정렬 알고리즘인 선택(Select)/버블(Bubble)/삽입(Insert) 정렬이 존재하고, 고급 정렬 알고리즘에는 분할과 정복 알고리즘인 병합(merge)/퀵(quick) 정렬과 힙(heap) 정렬 그리고 기수(Radix) 정렬이 존재한다.

정렬 알고리즘 분류

1. Stable 정렬 알고리즘

   정렬할 자료들(입력 자료) 중 동일한 두 자료의 상대적인 위치가 정렬 후에도 유지되는 정렬 알고리즘

2. In-place 정렬 알고리즘

   입력(정렬할 자료)을 저장하는 메모리 공간 의외에 추가로 사용하는 메모리 공간이 O(1)인 정렬 알고리즘

 

---

선택 정렬(Selection Sort)

1.  각 루프마다 최대(최소) 원소를 찾는다
2.  최대(최소) 원소와 마지막(가장 앞에 있는) 원소를 교환한다
3.  마지막(가장 앞에 있는) 원소를 제외한다

    => 하나의 원소만 남을 때까지 위의 루프를 반복한다

 

let selectionSort = arr => {
	var leng = arr.length; // 길이
    
    for(let i = leng-1; i > 0; i--) { // leng-1 번 반복
    	let ind = 0;
        for(let j = 1; j <= i; j++) { // 비교하기 
        	if(arr[ind] < arr[j])
            	ind = j;
        }
        let tmp = arr[ind]; // ind와 i 교환
        arr[ind] = arr[i];
        arr[i] = tmp;
    }
}

 

특징 

• In-place 알고리즘 O
• Stable 알고리즘 X
• 시간복잡도: O(n2)

 

버블 정렬(Selection Sort)

1.  매 단계마다 처음부터 마지막까지 차레대로 인접한 두 원소를 비교하며 뒤에 있는 원소가 앞에 있는 원소보다 작은 경우 두 원소 교환
2. 각 단계 수행 후 최대값이 마지막으로 이동, 마지막 원소는 정렬대상에서 제외
3. 만약 끝까지 가면서 교환이 일어나지 않았으면 정렬이 되어 있는 상태

    => 인접한 두 개의 원소를 차례대로 비교하면서 정렬하는 방식

 

let bubbleSort = arr => {
	let leng = arr.length;
    
    for(let i = leng-1; i > 0; i--) {
    	for(let j = 0; j < i; j++) {
        	if(arr[j] > arr[j+1]) { // 교환
            	let tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
           	}
        }
	}
}

 

특징 

• In-place 알고리즘 O
• Stable 알고리즘 O
• 시간복잡도: O(n2)

 

개선된 버블 정렬(Selection Sort)

   - 버블 정렬의 3번째인 끝까지 교환이 일어나지 않으면 정렬되어 있다는 사실을 반영하여 불필요한 검색을 줄이는 방법

  

  => 버블 정렬의 시간을 줄일 수 있다

 

let bubbleSort_2 = arr => {
	let leng = arr.length; // 길이
    
    for(let i = leng-1; i > 0; i--) {
    	let sorted = true; // 정렬 여부 판단 변수
        for(let j = 0; j < i; j++) {
        	if(arr[j] > arr[j+1]) {
            	let tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
                sorted = false;
            }
        }
        if(sorted) // 정렬되어 있으면 
        	break;
    }
}
            	

 

특징 

• 최악의 경우 시간복잡도: O(n2) -> 역순으로 정렬되어 있는 경우
• 가장 좋은 경우 시간: O(n) -> 정렬되어 있는 경우

 

삽입 정렬(Insertion Sort)

  - 0번 index 부터 i-1번 index 까지 정렬되어 있을 때 arr[i]까지 포함하여 정렬하는 알고리즘 

 

  => 0번 부터 특정 인덱스까지 계속 정렬해주면서 그다음 수를 정렬된 곳이 끼워넣는 것(그래서 삽입인듯....?) 

 

let selectionSort = arr => {
	let leng = arr.length;
	
    for(let i = 0; i < leng; i++) { // 차례대로 삽입하여 정렬
    	let tmp = arr[i];
        for(let j = i=1; j >= 0; j--) { // 정렬되어 있는 것에 삽입
        	if(arr[j] > tmp) {
            	arr[j+1] = a[j];
            else
            	break;
        }
        arr[j+1] = tmp;
    }
 }

 

특징 

• 최악의 경우 시간복잡도: O(n2) -> 역순으로 정렬되어 있는 경우
• 가장 좋은 경우 시간복잡도: O(n) -> 정렬되어 있는 경우
• 평균적인 경우 시간복잡도: O(n2)

 

 

Summary

	Best Case	Worst Case	Average Case	Stable	In-Place
Selection Sort	O(n2)	O(n2)	O(n2)	X	O
Bubble Sort	O(n2) => O(n) 개선	O(n2)	O(n2)	O (같으면)	O
Insertion Sort	O(n)	O(n2)	O(n2)	O (같으면)	O