[알고리즘] 정렬 - 기초 정렬 3대장(선택정렬, 버블정렬, 삽입정렬)

안녕하세요.

알고리즘의 정렬, 그 중에서도 간단하고 이해하기 쉬운 3대장인 선택정렬, 버블정렬, 삽입정렬에 대해 알아보겠습니다.

 

---

0. 정렬 알고리즘이란?

정렬 알고리즘은 sorting으로, 원소들을 일정한 순서대로(오름차순, 내림차순) 열거하는 알고리즘을 의미합니다.

 

 

1. 선택정렬(Selection Sort)

1) 아이디어

1. 각 루프마다 최대원소를 찾고, 최대원소와 마지막에 있는 원소와 교환한다.
2. 그리고 마지막에 있는 원소를 제외한다.
3. 하나의 원소만 남을 때까지 위의 루프를 반복한다.
각 회차별 마지막에 있는 원소의 자리를 "선택" 하고, 그 자리에 해당하는 값을 찾기 위해 비교한다고 보면 된다. 

 

2) 코드

function selectionSort(arr){
        let answer=arr;
        for(let i=0; i<arr.length; i++){
           let idx=i;
           for(let j=i+1; j<arr.length; j++){
               if(arr[j]<arr[idx]) idx=j; // 최대값인 원소를 찾는다.
           }
           [arr[i], arr[idx]] = [arr[idx], arr[i]]; //회차의 최대값과 마지막 원소와 교환한다.
        } 
        return answer;
 }

 

3) 시간복잡도

• 최선의 경우이든, 최악의 경우이든 이중 for문을 다 돌아야함. 
• (n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2  :  O(n²)

 

 

2. 버블정렬(Bubble Sort)

1) 아이디어

1. 매 단계마다 처음부터 마지막까지 차례대로 인접한 두 원소를 비교하여, 뒤에 있는 원소가 앞의 원소보다 작은 경우 두 원소를 교체한다.
2. 각 단계 수행 후, 최대 값이 마지막으로 이동하므로 마지막 원소는 정렬 대상에서 제외하고 진행한다.
비교하면서 교환을 할 때, 마치 모양이 버블 형태같아서 버블 정렬이라고 부른다.

 

2) 코드

function bubbleSort(arr) {
        let answer = arr;
        for (let i = arr.length - 1; i >= 0; i--) {
          for (let j = 0; j < i; j++) {
            if (arr[j] > arr[j + 1]) {
              [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
            }
          }
        }
        return answer;
}

 

3) 시간복잡도

• 최선의 경우: 자료가 이미 정렬되어 있는 경우 - O(n²)
  비교 횟수 : (n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2  
  교환 횟수: 일어나지 않음
  
• 최악의 경우 : 자료가 역순으로 정렬되어 있는 경우 - O(n²)
  비교 횟수 : (n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2   
  교환 횟수: (n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2  

 

4) 개선된 버블 정렬 알고리즘의 아이디어

1. 매 단계마다 처음부터 마지막까지 차례대로 인접한 두 원소를 비교하여, 뒤에 있는 원소가 앞의 원소보다 작은 경우 두 원소를 교체한다.
2. 각 단계 수행 후, 최대 값이 마지막으로 이동하므로 마지막 원소는 정렬 대상에서 제외하고 진행한다.
3. 기존의 버블 정렬알고리즘에서 한 차례를 돌다가, 교환이 일어나지 않았다면 그대로 정렬 완료된 상태이다. 

 

5) 개선된 버블 정렬 알고리즘의 코드

function solution(arr) {
     let answer = arr;
     for (let i = arr.length - 1; i >= 0; i--) {
		 let sorted = true; // 정렬 완료된 상태라 가정
         for (let j = 0; j < i; j++) {
            if (arr[j] > arr[j + 1]) {
              [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
			  sorted=false; // 교환이 있으면 정렬이 완료되지 않은 것임.
            }
          }
		  if(sorted){ // 교환이 일어나지 않은 경우
			break;
		  }
     }
     return answer;
}

 

6) 개선된 버블 정렬 알고리즘의 시간 복잡도

• 최선의 경우: 자료가 이미 정렬되어 있는 경우 - O(n)
  비교 횟수 : n
  교환 횟수: 일어나지 않음
  
• 최악의 경우 : 자료가 역순으로 정렬되어 있는 경우 - O(n²)
  비교 횟수 : (n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2   
  교환 횟수: (n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2  

 

 

 

3. 삽입정렬(Insertion Sort)

1) 아이디어

arr 배열에서, arr[0] 부터 a[i-1]까지 정렬되어 있을 때, a[i] 까지 포함하여 a[i]가 들어갈 곳을 삽입시켜 정렬하는 알고리즘.

 

2) 코드

function solution(arr) {
	let answer = arr;
	for (let i = 1; i < arr.length; i++) {
		let temp = arr[i]
		let j;
		for (j = i-1; j >= 0; j--) {
			if(arr[j] > temp) arr[j+1] = arr[j]
			else break;
		}
		arr[j+1] = temp;
	}
	return answer;
}

3) 시간복잡도

• 최선의 경우: 자료가 이미 정렬되어 있는 경우 - O(n)
  한번씩 밖에 비교를 안함.
  
• 최악의 경우 : 자료가 역순으로 정렬되어 있는 경우 - O(n²)
  (n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2