[알고리즘 공부] 정렬

정렬(Sorting)

 

 이번에는 이전 탐색 알고리즘에 이어서 <이코테> 내용을 바탕으로 "정렬" 알고리즘에 대해 알아보도록 하겠습니다. 우선 정렬(Sorting)이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 의미합니다. 프로그램에서 데이터를 가공할 때 오름 차순 혹은 내림차순 등 다양한 방식으로 정렬해서 사용하는 경우가 있기 때문에 이 알고리즘은 프로그램을 작성할 때 가장 많이 사용되는 알고리즘 중 하나라고 명시되어 있습니다. 그리고 정렬 알고리즘으로 데이터를 정렬하면 다음에 배울 이진 탐색(Binary Search)가 가능해진다고 하네요! 그리고 정렬 알고리즘은 대표적으로 선택, 삽입, 퀵 그리고 계수 정렬 등의 종류가 있는 데, 일단 책의 내용에 따라 이번에는 4개의 정렬 알고리즘에 대한 간단한 설명과 코드를 살펴보도록 하겠습니다. 

 

선택 정렬 (Seletion Sort)

 선택 정렬은 반복적으로 리스트를 순회하며 가장 작은(또는 가장 큰) 원소를 찾아 선택하고 현재 선택된 원소와 교환하는 방식입니다. 즉, 첫번째 위치에 가장 작은 원소, 두 번째 위치에 두 번째로 작은 원소를 배치하는 식으로 수행합니다.

 

삽입 정렬 (Insertion Sort)

 각 반복에서 하나의 입력 원소를 적절한 위치에 '삽입'하여 정렬된 리스트를 만듭니다. 이미 정렬된 부분의 적절한 위치에 새 원소를 삽입하기 때문에 각원소가 적절한 위치를 찾을 때까지 이동합니다.

 

퀵 정렬 (Quick Sort)

 '분할 정복' 전략을 사용하는 퀵 정렬은 피벗(pivot)이라고 불리는 원소를 선택하고 피벗보다 작은 원소는 모두 피벗의 왼쪽, 큰 원소는 모두 오른쪽으로 이동시킵니다. 이 과정은 재귀적으로 반복되어서 각 부분 리스트도 동일한 방식으로 정렬됩니다. 

 

계수 정렬 (Counting Sort)

  일반적인 비교 정렬 알고리즘이 아니며, 위 알고리즘은 입력 배열의 각 원소가 몇 번 등장하는지 세어서, 이 정보를 사용해 배열을 직접 정렬하는 방식입니다. 원소의 값이 정수이고, 특정 범위 내에 있을 때 효과적으로 사용됩니다. 

---

선택 정렬

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        # 가장 작은 원소의 인덱스를 찾음
        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]

# 예제 사용
array = [64, 25, 12, 22, 11]
selection_sort(array)
print("정렬된 배열:", array)

---

삽입 정렬

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        # 이전 요소들을 비교하며 적절한 위치 찾기
        j = i-1
        while j >=0 and key < arr[j] :
                arr[j+1] = arr[j]
                j -= 1
        arr[j+1] = key

# 예제 사용
array = [12, 11, 13, 5, 6]
insertion_sort(array)
print("정렬된 배열:", array)

---

퀵 정렬

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]  # 피벗 설정
    left = [x for x in arr if x < pivot]  # 피벗보다 작은 요소
    middle = [x for x in arr if x == pivot]  # 피벗과 같은 요소
    right = [x for x in arr if x > pivot]  # 피벗보다 큰 요소
    return quick_sort(left) + middle + quick_sort(right)

# 예제 사용
array = [3, 6, 8, 10, 1, 2, 1]
print("정렬된 배열:", quick_sort(array))

---

 

계수 정렬

 

def counting_sort(arr):
    max_val = max(arr)
    m = max_val + 1
    count = [0] * m                
    
    for a in arr:
        count[a] += 1             # 각 숫자의 개수 세기
    i = 0
    for a in range(m):            
        for c in range(count[a]):  # 개수만큼 숫자를 결과에 추가
            arr[i] = a
            i += 1
    return arr

# 예제 사용
array = [4, 2, 2, 8, 3, 3, 1]
print("정렬된 배열:", counting_sort(array))

 

---

마무리

 이번에는 정렬 문제를 풀어보기 전에 정렬에 대해서 간단히 알고 정렬 알고리즘에 대해 간단히 살펴보았습니다. 아직 심화 과정까지 갈 길이 멀고 멀었지만 그래도 하나씩 알아가는 과정에서 얼핏 스쳐지나간 문제들이 떠오르기 시작합니다. 그러면서 무작정 돌진했던... 예전의 저의 모습을 떠올리며, 다시 한 번 더 기초가 탄탄해야함을 깨닫게 됩니다. 시간은 아직 충분하니 차분하게 앞으로 나아가도록하겠습니다. 그럼 이번 글은 여기서 마무리하도록 하겠습니다.

 

 

참 고

2023.12.08 - [IT/관련 정보] - [코딩 테스트] 이것이 취업을 위한 코딩테스트다 with 파이썬

[코딩 테스트] 이것이 취업을 위한 코딩테스트다 with 파이썬