[파이썬 알고리즘] 정렬 알고리즘(선택정렬, 삽입정렬, 병합정렬, 퀵정렬)

정렬 알고리즘 : 특정 기준에 따라 데이터를 일정한 순서가 되도록 배열하는 것

대부분 O(n²), O(n log n)의 시간 복잡도를 가짐

O(n²) 정렬 알고리즘은 구현은 쉽지만 정렬 속도가 느림.

정렬 함수 : sort(), sorted() - 시간복잡도 : O(n log n)

정렬 알고리즘 종류
1. 선택 정렬
2. 삽입 정렬
3. 병합 정렬
4. 퀵 정렬

---

선택 정렬

선형 탐색을 통한 정렬 과정

선택 정렬 예시

numbers = [6, 8, 5, 2, 4, 3, 1]   #주어진 숫자
n = len(numbers)   #리스트 길이 = 7

for i in range(n):   #i는 0 ~ 6까지 총 7번 반복
    min_idx = i   #현재 i가 최소값 설정
    for j in range( i+1, n):   # i+1 부터 끝까지 비교
        if numbers[j] < numbers[min_idx]:   # j가 최소값보다 작을경우
            min_idx = j   # j를 최소값으로 업데이트
    numbers[i], numbers[min_idx] = numbers[min_idx], numbers[i]   # i와 최소값의 자리 교환

print(numbers)


출력 :

[1,2,3,4,5,6,8]


시간복잡도 : O(n²)

반응형

예시 코드 설명 이미지_선택정렬

예시 코드 설명 이미지_선택정렬

---

삽입정렬

앞 요소의 순서를 유지하면서 요소를 하나씩 올바른 위치에 삽입 하는 방식

정렬된 리스트에 이용할 경우 시간 복잡도는 O(n)에 가깝다.

삽입정렬 예시

numbers = [6, 8, 5, 2, 4, 3, 1]   #주어진 숫자
n = len(numbers)   #리스트 길이 = 7

for i in range(n):   #i는 0 ~ 6까지 총 7번 반복
    key = numbers[ i ]   #현재 삽입할 숫자
    j = i - 1   # 정렬된 구간의 마지막 인덱스 / key 보다 앞쪽 정렬된 구간을 검사할 인덱스
       
    while j >= 0 and key < numbers[ j ] :    
            numbers[ j + 1 ] = numbers [ j ]   #오른쪽으로 한칸 밀기
            j -= 1   #왼쪽으로 이동 / 빈공간을 만들어 j가 들어갈 공간을 확보
    numbers[ j + 1] = key   #key를 올바른 자리에 삽입
print(numbers)


출력 :

[1,2,3,4,5,6,8]


시간복잡도 : 최선의 경우 O(n) / 최악의 경우 O(n²)

예시 코드 설명_삽입정렬

728x90

예시 코드 설명_삽입정렬

버블 정렬 알고리즘 

인접한 두 요소 중 더 큰 값을 뒤로 보내는 과정을 반복하는 정렬 알고리즘

거품이 물 위로 올라오는 것 과 유사하게 요소가 이동하여 버블 정렬이라고 한다.

버블정렬 예시

numbers = [5,4,3,2,1]
n = len(numbers)

for i in range(n) :
    for j in range(0 , n - i - 1) :
        if numbers[ j ] > numbers[ j +1 ] :
            numbers[ j ], numbers[ j+1 ] = numbers[ j+1 ], numbers[ j ]
    print(f"{ i + 1}번 반복문 완료 후 : {numbers}")
print(numbers)


출력 :
1번 반복문 완료 후 : [4,3,2,1,5] 
2번 반복문 완료 후 : [3,2,1,4,5] 
3번 반복문 완료 후 : [2,1,3,4,5] 
4번 반복문 완료 후 : [1,2,3,4,5] 
5번 반복문 완료 후 : [1,2,3,4,5] 
[1,2,3,4,5]


시간 복잡도 : O(n²)

---

병합 정렬

나눌 수 없을 때 까지 분할 후 재귀함수로 병합을 진행하며 정렬하는 방식

base case는 요소의 갯수가 1개 이하인 경우 설정하여 리스트를 반환한다.

병합 정렬 예시


def merge_sort(numbers):    
    if len(numbers) <= 1 :    
        return numbers           #리스트의 길이가 1 이하일 경우 그대로 리턴
    mid = len(numbers) // 2    #리스트를 반으로 쪼갠다.
    left_half = merge_sort(numbers[:mid])  #왼쪽 리스트에 재귀호출
    right_half = merge_sort(numbers[mid:])  #오른쪽 리스트에 재귀호출

    merged = [ ]    #병합된 정렬 결과를 저장할 빈 리스트
     i = j = 0  #왼쪽, 오른쪽의 리스트 인덱스를 초기화

    while i < len(left_half) and j<len(right_half):
        if left_half[i] < right_half[j]:    #왼쪽 현재값이 오른쪽 현재값보다 작을 경우
            merged.append(left_half[i])   #왼쪽 현재값을 merged에 추가
            i += 1                                      #그 다음 번째 값으로 한칸 옮긴다.
        else:                                               # 왼쪽 현재값이 오른쪽 현재값보다 클 경우
            merged.append(right_half[j])     #오른쪽 현재 값을 merged에 추가
            j += 1                                         #오른쪽 현재값을 그 다음번째 값으로 한칸 옮긴다.

    while i < len(left_half):            #병합 종료 후 오른쪽이 빈 리스트일 경우 왼쪽 남은 값을 순서대로 merged에 추가한다.
        merged.append(left_half[i])
        i += 1

    while j < len(right_half):         #병합 종료 후 왼쪽이 빈 리스트일 경우 왼쪽 남은 값을 순서대로 merged에 추가한다.
        merged.append(right_half[j])
        j += 1
    return merged

numbers = [4,2,3,1]
sorted_numbers = merge_sort(numbers)
print(sorted_numbers)


출력 : [1,2,3,4]

예시 코드 설명 _ 병합정렬

---

SMALL

퀵 정렬

기준(pivot)으로 더 작은 그룹, 큰 그룹을 나누고 그 그룹에 같은 과정을 반복해 정렬하는 방식

분할 과정에서 정렬이 점진적으로 진행 되기 때문에 분할이 종료가 되면 정렬이 완료가 된다.

시간복잡도는 경우에따라 최소 O(log n)단계 에서 최대 O(n)단계가 필요하다.

최악의 경우인 O(n²)은 기준(pivot)이 최대값 또는 최소값으로 선택 되는 경우이다.

def quick_sort(numbers):
    if len(numbers) <= 1 :
        return numbers                        #base case 설정 ( 1이하일 경우 numbers로 돌아간다)

    pivot = numbers[len(numbers) // 2]   #기준점 설정
    left = [ ]
    right = [ ]
    middle = [ ]
   
    for x in numbers :
        if x < pivot :
            left.append(x)           # x가 pivot보다 작을 경우 left 리스트에 추가 한다.
        elif x > pivot :
            right.append(x)        # x가 pivot보다 클 경우 right 리스트에 추가 한다.
        else:
            middle.append(x)    # 그 외 기준숫자와 동일할경우 middle리스트에 추가한다.
    return quick_sort(left) + middle + quick_sort(right)    

numbers = [4,3,7,2,4,1,4,6,5]
sorted_numbers = quick_sort(numbers)
print("정렬 숫자 : ", sorted_numbers)


출력 :
정렬 숫자 : [1, 2, 3, 4, 4, 4, 5, 6, 7]

예시 코드 설명 - 퀵 정렬