[Week01] 알고리즘 - 정렬01

정렬01

✅ 파이썬 내장함수

• arr.sort() : 오름차순 정렬
• arr.sort(reverse = True) : 내림차순 정렬

#백준11650 - key값으로 정렬

arr = []
for _ in range(int(input())):
    arr.append(list(map(int, input().split())))
 
arr.sort(key=lambda x:(x[0], x[1]))
#x[0]의 크기를 기준으로 정렬, 값이 같다면 x[1]으로 비교
 
for e in arr:
    print(str(e[0]) + " " + str(e[1]))

 

 

✅ 버블 정렬

: 서로 인접한 두 원소를 검사하여 정렬한다. (swap)

시간복잡도 O(N^2)

def bubble_sort(arr):
    for i in range(len(arr) - 1, 0, -1): #len(arr)-1 에서 0까지 역순으로
        for j in range(i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

 

✅ 선택 정렬 

: 리스트에 최솟값을 찾아 맨 앞에 위치시킨다. (swap)

시간복잡도 O(N^2)

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]

 

✅ 삽입 정렬

: 손안에 카드(key)를 비교하는 방식. 두번째 원소부터 그 앞 쪽의 원소들을 확인해 삽입할 위치 확인하여 하나씩 뒤로 미룬다.

시간복잡도 O(N^2)

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]

 

#백준2750 - 버블정렬, 선택정렬, 삽입정렬을 이용해 해결가능

 

✅ 셀 정렬

: 삽입 정렬을 보안한 알고리즘. 요소가 삽입될때 이웃한 위치로만 이동 가능하다는 삽입 정렬의 단점을 보안한다.

: 정렬해야 할 리스트의 각 k번째 요소를 추출해서 부분 리스트를 만든다. 이때 k를 '간격'이라고 한다. 

시간복잡도 O(N^1.5)

def shell_sort(arr):
    N = len(arr)
    k = N // 2
    while k > 0:
        for i in range(k, N):
            temp = arr[i]
            j = i - k
            #삽입정렬
            while j >= 0 and arr[j] > temp:
                arr[j + k] = arr[j]
                j -= k
            arr[j + k] = temp
        k //= 2

어렵다!

 

 

오늘도 열코 ❗️