정렬 알고리즘의 종류

정렬 알고리즘의 종류는 무수히 많지만, 오늘은 기본(단순)정렬 알고리즘 중 버블, 선택, 삽입 정렬을 알아보기로 하자.

보통 기본정렬에 속하는 알고리즘은 효율이 좋지 않기 때문에 자주 사용하지는 않지만 작은 수(30이하의 수)에서는 효과적일 수 있다.

1.버블정렬(Bubble Sort)

두 인접한 원소를 검사하여 정렬하는 방법이다.
시간 복잡도가 O(n²)로 상당히 느리지만, 코드가 단순하기 때문에 교육용으로 좋은 알고리즘 이다.

[2,5]  => arr[0],arr[1] 

[5,4,2]
[4,2,5] => arr[0],arr[1] &  arr[1],arr[2]
[2,4,5] => arr[0],arr[1] &  arr[1],arr[2]
	 
[5,2,3,1]
[2,3,1,5] => arr[0],arr[1] &  arr[1],arr[2] & arr[2],arr[3]
[2,1,3,5] => arr[0],arr[1] &  arr[1],arr[2] & arr[2],arr[3]
[1,2,3,5] => arr[0],arr[1] &  arr[1],arr[2] & arr[2],arr[3]

  for (i = 0; i < 데이터길이 - 1; i++)
	   for (j = 0; j < 데이터길이 - i; j++)
		if(앞데이터 > 뒤데이터){
          	swap(앞데이터, 뒤데이터)
        }

✍🏻 첫번째 턴에서 가장 큰 값이 무조건 맨 뒤로 가게 되므로 다음 정렬시 마지막값들의 비교는 불필요하다.

[2,5]  => arr[0], arr[1] 

[5,4,2]
[4,2,5] => arr[0],arr[1] &  arr[1],arr[2]
[2,4,5] => arr[0],arr[1] 
	 
[5,2,3,1]
[2,3,1,5] => arr[0],arr[1] &  arr[1],arr[2] & arr[2],arr[3]
[2,1,3,5] => arr[0],arr[1] &  arr[1],arr[2] 
[1,2,3,5] => arr[0],arr[1]

  for (i = 0; i < 데이터길이 - 1; i++)
	   for (j = 0; j < 데이터길이 - i -1 ; j++)
		if(앞데이터 > 뒤데이터){
          	swap(앞데이터, 뒤데이터)
        }

✍🏻 이미 정렬되어있는 경우 불필요한 정렬을 막아주자!

[1,2,3,5] => arr[0],arr[1] &  arr[1],arr[2] & arr[2],arr[3]

for (i = 0; i < 데이터길이 - 1; i++)
  let swap = false;
   for (j = 0; j < 데이터길이 - i -1 ; j++)
	if(앞데이터 > 뒤데이터){
       	swap(앞데이터, 뒤데이터)
       	let swap = true;
      }
	if(swap === false) break;

♻️ swap 이 한번도 일어나지 않을 경우는 이미 정렬이 완료된 상태임으로 로직에서 빠져나올 수 있게 한다.

알고리즘 분석

• 반복문이 2개 O(n²)
• 완전 정렬이 되어있는 경우 O(n)

선택정렬(Selection Sort)

1. 주어진 데이터 중, 최소값을 찾음
2. 찾은 최소값을 맨 앞 데이터와 순서를 바꿈

[5,4,3,1] => 최소값인 1을 가장 앞으로 정렬
[1,4,3,5] => 다음 최소값인 3를 그 다음으로 정렬
[1,3,4,5] => 다음 최소값인 4를 그 다음으로 정렬
[1,3,4,5] => 다음 최소값인 5를 그 다음으로 정렬

for (i = 0; i < 데이터길이 - 1; i++)
  lowest = i(기준점);
for (j = lowest + 1; j < 데이터길이; j++) {
  if (arr[lowest] > arr[j]) {
    lowest = j;
  }
}
swap(arr[lowest], arr[j]);

알고리즘 분석

• 반복문이 2개 O(n²)

삽입정렬(Insertion Sort)

자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.
기준점은 항상 두번째 배열의 수이다.

[5,3] => arr[1],arr[0]

[5,3,2] => 두번째 수 3과 5 비교 후 swap
[2,3,5] => 세번째 수 2와 3,5 비교 후 swap

[5,3,2,4] => 두번째 수 3과 5 비교 후 큰 수인 5와 swap
[3,5,2,4] => 세번째 수 2와 3,5 비교 후 큰 수인 3과 5와 swap
[2,3,5,4] => 네번째 수 4와 2,3,5 비교후 큰 수인 5와 swap
[2,3,4,5] 

for (i = 0; i < 데이터길이 - 1; i++)
for (j = i + 1 ; j >= 0 ; j--) {
     if(arr[j] < arr[j-1]){
       		swap(arr[i], arr[j-1])
     }else{
	     break;	
     }
}

알고리즘 분석

• 반복문이 2개 O(n²)
• 완전 정렬이 되어있는 경우 O(n)

reference

정렬 시각화
선택정렬 위키피디아
거품정렬 위키피디아