1. 버블 정렬 (Bubble Sort)

버블 정렬은 인접한 두 요소를 비교하고, 필요에 따라 위치를 바꿔서 정렬을 수행하는 간단한 정렬 알고리즘입니다. 각 패스마다 가장 큰(혹은 작은) 요소가 리스트의 끝으로 '버블'처럼 이동합니다. 이 과정이 반복되며, 전체 리스트가 정렬될 때까지 계속됩니다.

• 과정:
  1. 리스트의 처음부터 시작하여 인접한 두 요소를 비교합니다.
  2. 만약 첫 번째 요소가 두 번째 요소보다 크다면, 두 요소의 위치를 교환합니다.
  3. 이 과정을 리스트 끝까지 반복합니다.
  4. 위의 과정을 리스트가 정렬될 때까지 반복합니다.
• 장점:
  • 구현이 매우 간단합니다.
  • 작은 데이터셋에 대해서는 효율적일 수 있습니다.
• 단점:
  • 최선, 평균, 최악의 경우 모두 시간 복잡도가 O(n²)입니다.
  • 매우 비효율적이며, 실제로 거의 사용되지 않습니다.

2. 퀵 정렬 (Quick Sort)

퀵 정렬은 '분할 정복' 전략을 사용하는 효율적인 정렬 알고리즘입니다. 리스트에서 하나의 요소(피벗)를 선택하고, 이 피벗보다 작은 요소들은 피벗의 왼쪽에, 큰 요소들은 피벗의 오른쪽에 배치되도록 리스트를 분할합니다. 이 과정을 재귀적으로 반복하여 리스트를 정렬합니다.

• 과정:
  1. 피벗을 선택합니다(피벗 선택 방법은 다양합니다).
  2. 피벗을 기준으로 리스트를 두 부분으로 나눕니다(피벗보다 작은 값, 피벗보다 큰 값).
  3. 분할된 부분 리스트에 대해 재귀적으로 퀵 정렬을 적용합니다.
  4. 재귀 호출이 끝나면 전체 리스트가 정렬됩니다.
• 장점:
  • 평균 시간 복잡도는 O(n log n)으로, 매우 효율적입니다.
  • 내부(in-place) 정렬이므로 추가 메모리 사용이 적습니다.
• 단점:
  • 최악의 경우(이미 정렬된 배열에서 첫 번째 또는 마지막 요소를 피벗으로 선택한 경우) 시간 복잡도가 O(n²)입니다.
  • 재귀적으로 구현되므로, 스택 오버플로우가 발생할 수 있습니다(비록 이는 재귀 깊이를 제한하여 해결할 수 있음).

3. 선택 정렬 (Selection Sort)

선택 정렬은 리스트에서 가장 작은(또는 가장 큰) 요소를 찾아내어 리스트의 시작 부분으로 이동시키는 방식으로 정렬하는 알고리즘입니다. 이 과정을 반복하여 리스트를 정렬합니다.

• 과정:
  1. 리스트에서 최소값(또는 최대값)을 찾습니다.
  2. 이 최소값을 리스트의 첫 번째 요소와 교환합니다.
  3. 리스트의 나머지 부분에 대해 이 과정을 반복합니다.
  4. 리스트가 정렬될 때까지 이 과정을 계속합니다.
• 장점:
  • 구현이 간단합니다.
  • 스왑 횟수가 적어 정렬하는 동안 위치 교환에 따른 비용이 적습니다.
• 단점:
  • 시간 복잡도는 O(n²)로, 버블 정렬과 마찬가지로 비효율적입니다.
  • 큰 리스트에 대해서는 매우 비효율적입니다.

4. 삽입 정렬 (Insertion Sort)

삽입 정렬은 리스트의 요소를 하나씩 선택하여 이미 정렬된 리스트의 올바른 위치에 삽입하면서 정렬하는 방식입니다. 첫 번째 요소는 이미 정렬된 것으로 간주하며, 두 번째 요소부터 시작합니다.

• 과정:
  1. 리스트의 첫 번째 요소는 정렬된 것으로 간주합니다.
  2. 두 번째 요소부터 시작하여, 해당 요소가 앞의 정렬된 부분 리스트에 삽입될 위치를 찾습니다.
  3. 해당 위치에 삽입한 후, 그 뒤의 요소들을 오른쪽으로 이동시킵니다.
  4. 리스트의 마지막 요소까지 이 과정을 반복합니다.