[코딩노트-알고리즘] 정렬 한 번에 보기

💡 이 포스트에는 알고리즘 - 정렬관련된 내용을 정리했다.
(제가 모를 때 보려고 후다닥 보려고 정리했으므로 양해바랍니다!)

정렬이란?

정렬 알고리즘은 컬렉션(대상)의 항목을 재배열하는 방법을 의미한다.

여기서는 자바스크립트와 배열을 위주로 설명하며, 정렬 예제는 오름차순이라고 가정한다.

• 정렬을 왜 배우는가?
  • 정렬이 프로그래밍에서 흔하게 사용되기 때문이다.
  • 정렬하는 방법에는 여러가지가 있고 각자 장단점이 있다. -> 각자 사용할 때가 있다.
  • 전형적인 면접 주제이다.

참고) 가장 기본적이고 쉬운 정렬: 자바스크립트 내장 정렬 sort()
그냥 사용하면 유니코드 순서대로 오름차순 정렬한다.
안에 콜백함수를 전달하면 그것대로 정렬한다.

//sort의 콜백함수의 예제        
//숫자 오름차순 정렬
function compareAandB1(a,b){
  return a-b; //음수이면 a가 먼저, 양수이면 b가 먼저 정렬된다.
}
//숫자 내림차순 정렬
function compareAandB2(a,b){
  return b-a; 
}
//문자열 길이 오름차순 정렬
function compareLength(a,b){
  return a.length - b.length; 
}

정렬의 종류

정렬에는 여러 가지 방법이 있지만, 기장 기본적인 정렬과 많이 언급되서 꼭 알아야 하는 정렬만 정리했다.

• 버블, 선택, 삽입 : 기본적인 정렬 알고리즘이다.
  효율성이 떨어지기는 한다. 그러나! 학습을 위해 알아야 한다.
• 병합(합병), 퀵 : 기본 3가지 정렬을 알아야 학습할 수 있다.

각 정렬은 아래의 사이트에서 보면 직관적으로 이해할 수 있다.
🔗 https://visualgo.net/en/sorting

1. 버블 정렬 bubble sort

• 특징:
  위아래로 움직이는 것 같아서 거품같다고 한다.(?)
  다소 비효율적인 알고리즘이다.
• 방법:
  두 숫자를 차례대로 비교하여 큰 숫자를 뒤로 보내고, 반복한다.

2. 선택정렬 selection sort

• 특징:
  최솟값을 계속 ‘선택’하여 정렬한다.
• 방법:
  • 맨 처음 값을 point로 잡는다.
  • 그 다음 값부터 마지막까지 최솟값을 찾는다.
  • 최솟값을 point와 비교한다.
  • 만약 최솟값이 point 보다 작다면 point와 최솟값 자리를 바꾼다.

3. 삽입정렬 insertion sort

• 특징 :
  요소를 알맞은 위치에 ‘삽입’해가면서 정렬한다. 좀 더 효율적이다.
• 방법:
  • 첫번째 요소를 정렬되었다고 가정한다.
  • 두번째 요소를 확인해 첫번째 요소중 맞는 자리로 삽입한다.
  • 다음 요소를 확인한다.
  • 정리하자면 검사하는 요소의 왼쪽은 모두 정렬된 것이다.
  • 이 과정을 모두 정렬될 때까지 반복한다.

4. 병합(합병) 정렬 merge sort

• 특징:
  • 분할, 정렬, 합병을 전부 사용한다.
  • 분할 정복 알고리즘이라는 것을 알아야 한다.
  • 합병 정렬을 알려면 재귀, 버블, 선택, 삽입 정렬 전부 알아야 한다.
• 방법:
  • 먼저 전체 배열을 모두 2개로 나눠가며 분할한다. 각 배열의 요소가 1개가 될 때까지 분할한다.
  • 분할된 배열의 요소가 1개가 되면 그 요소는 정렬된 것이다.
  • 분할된 배열을 정렬하며 병합한다.
  • 이미 정렬된 배열들을 병합하려면 각 인덱스끼리 비교한다. 이는 좀 더 효율적이다.
  • 이런 방식으로 분할된 배열들이 하나가 되면 나머지 병합하지 못한 배열도 같은 방식으로 병합한다. 이 과정은 주로 재귀를 사용한다.

5. 퀵 정렬 quick sort

• 특징:
  • 퀵 정렬을 알려면 마찬가지로 재귀, 병합, 버블, 선택, 삽입 정렬을 알아야 한다.
  • 기준인 피벗 포인트라는 개념이 존재한다.
  • 피벗 포인트를 기준으로 정렬하는 방법은 검색해보면 차이가 있다.
• 방법:
  • 첫 번째 요소 혹은 랜덤한 요소를 피벗으로 잡는다. 여기서는 첫번째 요소로 한다.
  • 두번째 요소부터 검사하여 피벗보다 크면 넘어가고, 작다면 앞으로 끌어온다.
    앞으로 끌어올 때 그 자리에 큰 값이 있다면 자리를 서로 바꾼다.
  • 이 과정이 한차례 끝나면, 피벗은 이미 정렬된 작은 요소들 중 제일 크므로 마지막으로 이동시켜 고정한다.
    이러면 피벗은 정렬된 것이다.
  • 다시 작은 요소들의 첫번째를 피벗으로 정한다.
  • 이 과정을 배열의 요소가 하나만 남을 때까지 반복한다.

알고리즘의 비교

각 알고리즘은 정렬 대상과 상황에 따라 장단점이 다르다.

• 자료가 정렬이 안된 상황: 병합, 퀵, 선택 정렬이 유리하다.
• 자료가 어느정도 정렬된 상황: 삽입과 버블이 유리하다.
• 자료가 거꾸로 정렬된 상황: 퀵, 병합이 유리하고, 그나마 선택 정렬이 빠르다.

아래 사이트를 참고하면 각 알고리즘이 어떤 상황에서 얼마나 빠른지 애니메이션으로 한 눈에 보며 비교할 수 있다.
🔗 https://www.toptal.com/developers/sorting-algorithms

이미지 자료 출처: https://sirpaulmcd.com/tutorials-cheat-sheets/data-structures-and-algorithms/sorting-algorithms/#selection-sort