[ Python ] 정렬 알고리즘

사실 파이썬에서는 sort, sorted를 지원하지만, 직접 구현해보자 이말입니다.

1. 선택정렬

1. 인덱스 0번부터 비교시작
2. 0번 뒤에 애들 중 가장 작은 값 찾기
3. 있으면 0번이랑 자리 바꾸고, 없으면 넘어간다.
4. 인덱스 1번~

시간복잡도는 O(n^2)

#1.선택알고리즘
arr1=[2,4,5,1,3]
def selection_sort(arr):
    for i in range(len(arr)-1):
        min_idx = i
        for j in range(i+1, len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx=j
        arr[i],arr[min_idx]=arr[min_idx],arr[i]
selection_sort(arr1)
print(arr1)

 

 

2. 삽입정렬

1. 삽입정렬은 1번 인덱스부터 시작한다. ( 0 아님)
2. 1번과 0번을 비교. 1번이 더 작으면 자리 바꾼다.
3. 2번 인덱스에서 시작.
4. 2번과 1번 비교 후 2번이 작으면 자리 바꿈.
5. 1번이 0번보다 작으면 자리 바꿈.
6. 3번인덱스 -> 2와 비교, 1, 0 ,...

시간복잡도

• 이미 정렬되어 있으면 O(n)
• 정렬이 필요하면 O(n^2)

#2.삽입정렬
arr2=[3,5,1,2,4]
def insertion_sort(arr):
    for end in range(1,len(arr)):
        for i in range(end,0,-1):
            if arr[i-1] > arr[i]:
                arr[i-1],arr[i] = arr[i],arr[i-1]
insertion_sort(arr2)
print(arr2)

 

3. 버블정렬

1. 1번 인덱스부터 시작
2. 1번과 0번 비교 후 자리 바꿈
3. 2번과 1번 비교 후 ,,,
4. 3번과 2번 ,,,
5. 4번과 3번,,,
6. 이를 (전체 배열 크기 - 현재까지 순환한 바퀴수) 만큼 반복

시간복잡도는 O(n^2)

#3.버블정렬
arr3=[2,5,3,1,4]
def bubble_sort(arr):
    for i in range(len(arr)-1,0,-1):
        for j in range(i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1]= arr[j+1], arr[j]
bubble_sort(arr3)
print(arr3)