[TIL] 정렬 - Sorting

정렬

• 데이터를 정해진 순서대로 나열하는 것으로 여러 기법이 있다.

 

1. 버블 정렬 (bubble sort)

  - 인접한 두 데이터를 비교하여 앞에 있는 데이터가 뒤에 있는 데이터보다 클 경우 자리를 바꾼다. 

  - 데이터가 n개일 경우 최대 n-1번의 로직을 적용한다.

  - 데이터 교환이 필요 없을 경우 (이미 정렬된 상태)가 존재한다. 

def bubble(data):
    for idx in range(len(data)-1):
        swap = False				
        for idx2 in range(len(data)-1-idx):
            if data[idx2] > data[idx2+1]
                data[idx2], data[idx2+1] = data[idx2+1], data[idx2]
                swap = True
        if swap == False:
            break			# 이미 정렬된 상태면 break
    return data

버블정렬의 시간복잡도?
- for문을 두번 돌리므로 O(n*n)
- 이미 완전정렬이 되어있을 경우라면 O(n)

 

2. 삽입 정렬 (insertion sort)

  - 두 번째 인덱스부터 시작한다.

  - 앞에 있는 데이터부터 비교해서 해당 인덱스의 키 값이 앞의 값보다 작으면 데이터의 값을 뒤의 인덱스로 복사한다.

  - 위의 과정을 해당 인덱스의 값보다 큰 데이터를 만날때까지 계속 반복한 후 마지막에 데이터를 이동한다.

 

def insertion(data):
    for idx in range(len(data)-1):	# 두 번째 인덱스부터 시작
        for idx2 in range(idx+1, 0, -1):
            if data[idx2] < data[idx2-1]:
                data[idx2], data[idx2-1] = data[idx2-1], data[idx2]
            else:
                break
    return data

삽입 정렬의 시간복잡도?
- for문을 두번 돌리므로 O(n*n)
- 이미 완전정렬이 되어있을 경우라면 O(n)

 

2. 선택 정렬 (selection sort)

  - 데이터의 최대/최소값을 찾아 해당 값을 데이터의 첫 번째 인덱스의 값과 교환한다.

  - 앞에서 교환된 위치를 제외한 나머지 데이터를 동일한 방법으로 반복한다.

 

def selection(data):
    for x in range(len(data)-1):
        minData = x
        for idx in range(x+1, len(data)):	# 최소값을 찾는 과정
            if data[minData] > data[idx]:
                minData = idx
                data[minData], data[x] = data[x], data[minData]
    return data

선택 정렬의 시간복잡도?
- for문을 두번 돌리므로 O(n*n)
- 이미 완전정렬이 되어있을 경우라면 O(n)

 

 

*본 내용은 패스트 캠퍼스 강의를 참고하였습니다.