정렬(1) - 선택, 삽입, 버블, 셸

정렬

주어진 데이터를 값의 크기 순서에 따라 재배치 하는것 (오름/내림차순)

내부 정렬 

• 정렬한 전체 데이터를 주기억장치에 저장한 후 정렬하는 방식

비교기반	데이터 분포 기반
두 데이터 값 전체를 비교해 어떤값이 큰지 작은지 결정하여 정렬	데이터의 분포 정보를 활용해 정렬
선택, 버블, 삽입, 셸, 합병, 퀵, 힙 정렬	계수, 기수, 버킷

안정적 Stable 정렬

• 같은 값을 갖는 데이터에 대한 정렬 전의 상대적인 순서가 정렬 후에도 그대로 유지되는 정렬 방식
• 입력
  • 5 1 2 3 6 2 4 
• 정렬 후
  • 1 2 2 3 4 5 6 (안정)
  • 1 2 2 3 4 5 6 (불안정) 

제자리 정렬 in-place

• 입력 배열 이외에 별도로 필요한 저장 공간이 상수 개를 넘지 않는 정렬 
• 입력 크기 n이 증가해도 추가적인 저장 공간 사용하지 않음 

---

선택 정렬 (Selection Sort)

• 전체 배열에서 가장 작은(또는 가장 큰) 값을 찾아 맨 앞의 값과 교환하는 방식으로 정렬함. 다음에는 두 번째 작은 값을 찾아 두 번째 위치와 교환하며 반복함.
• 1. 배열에서 가장 작은 원소를 선택한다.
  2. 선택한 원소를 배열의 맨 앞과 교환한다.
  3. 맨 앞을 제외한 나머지 배열에서 다시 가장 작은 원소를 선택하여 두 번째 위치와 교환한다.
  4. 위 과정을 배열 전체가 정렬될 때까지 반복한다.
• 성능과 특징
  • 입력 데이터의 순서에 민감하지 않음:  미정렬 부분에서 항상 (n-1) - i 번 비교 필요하므로 성능이 일정 
  • 시간 복잡도: 최선, 평균, 최악의 경우 모두 O(n2)
  • 제자리 정렬
  • 불안정 정렬 
    • 1 2 4 4 3 > 1 2 3 4 4  

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        min_index = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr

버블 정렬 (Bubble Sort)

• 인접한 두 원소를 비교하여 큰 값(또는 작은 값)을 오른쪽(또는 왼쪽)으로 이동시키면서 정렬함. 매 패스를 수행할 때마다 가장 큰 값이 맨 뒤에 확정됨.
• 1. 인접한 두 원소를 비교하여 큰 값을 뒤로 이동시킨다.
  2. 배열의 끝까지 반복하여 가장 큰 값을 배열의 마지막에 위치시킨다.
  3. 다음 패스에서는 이미 정렬된 마지막 값을 제외하고 다시 비교하여 정렬한다.
• 개선된 버블 정렬: 한 번의 패스 동안 교환이 한 번도 일어나지 않았다면 이미 정렬된 상태이므로 추가적인 패스를 중지할 수 있음.
• 성능과 특징
  • 최선의 경우 (이미 정렬된 경우) O(n)
  • 평균 및 최악의 경우 O(n2)
  • 안정적 정렬
  • 제자리 정렬

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr

삽입 정렬 (Insertion Sort)

• 배열을 정렬된 부분과 미정렬 부분으로 나누고, 미정렬 부분에서 데이터를 하나씩 꺼내어 정렬된 부분에서 적절한 위치를 찾아 삽입함.
• 1. 정렬된 부분과 미정렬 부분으로 나눈다.
  2. 미정렬 부분의 첫 번째 데이터를 선택한다.
  3. 선택한 데이터를 정렬된 부분에서 적절한 위치에 삽입한다.
  4. 위 과정을 반복하여 배열 전체를 정렬한다.
• 성능과 특징
  • 최선의 경우 (거의 정렬된 경우) O(n)
  • 평균 및 최악의 경우 O(n2)
  • 안정적 정렬
  • 제자리 정렬 

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

셸 정렬 (Shell Sort)

• 알고리즘: 삽입 정렬의 단점을 개선한 알고리즘으로, 멀리 떨어져 있는 원소를 비교하고 교환하여 한 번에 먼 거리를 이동시키는 방식으로 정렬함. 점점 간격(gap)을 줄여가며 삽입 정렬을 수행하는 방식
• 1. 적절한 간격(gap)을 선택한다.
  2. 선택된 간격만큼 떨어져 있는 원소들을 비교하여 교환한다.
  3. 간격을 점점 줄이며 위 과정을 반복한다.
  4. 간격이 1이 될 때까지 반복하면 마지막 단계는 일반 삽입 정렬과 같아짐.
• 성능과 특징
  • 삽입 정렬보다 성능이 크게 향상됨
  • 시간 복잡도는 gap(간격)의 크기 및 감소 방식에 따라 달라짐 (평균 ~ O(1.25) ~ O(1.5))
  • 일반적으로 불안정 정렬
  • 제자리 정렬

def shell_sort(arr):
    n = len(arr)
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap //= 2
    return arr