Python_수업 (4)

2024.04.09 (화)

 

정렬

목표 : 안정 정렬이 무엇인지!

1. 버블 정렬 (안정 정렬)

# 버블 정렬 코드
arr = [2, 4, 1, 3]  # 정렬하고자 하는 리스트의 길이가 4니까?

for i in range(len(arr)-1, 0, -1):  # 총 3회 시행, 
    for j in range(i): # 각 시행 횟수 안에서, 3 2 1 번씩 비교 할것 
        if arr[j] > arr[j+1]: # 내가 오른쪽 녀석보다 크다면?
            arr[j], arr[j+1] = arr[j+1], arr[j]  # 자리를 바꾼다!

print(arr)

'''
" > " 때문에 안정 정렬이 된다!!
'''

 

2. 카운팅 정렬 (안정 정렬)

• 어렵…
• 안정 정렬 보장법 기교 S 배열 (누적합 배열)
• step 1. 개수를 센다. step 2. 누적합 ← 어디있어야돼? 의 지표 step 3. 뒤에서부터 누적합에 물어본다. → 위치에 들어가면 누적합에서 하나씩 마이너스

# 카운팅 정렬 코드
nums = [4, 4, 2, 3, 5, 5, 1, 1, 5]

count = [0] * (max(nums) + 1)  # 갯수 세는 리스트
sorted_nums = [0] * len(nums)  # 정렬된 리스트의 원형 틀

'''여기까지 자료구조!!'''

for num in nums:  # 일단 몇개씩 있는지 카운트
    count[num] += 1

for i in range(1, len(count)):  # 누적합 -> 1부터 시작하는 것 중요!!
    count[i] = count[i] + count[i-1]

for j in range(len(nums)-1, -1, -1):  # 뒤의 자리부터 뽑아서,
    sorted_nums[count[nums[j]]-1] = nums[j] # 5가 튀어나오면 5의 위치에 뒤부터 삽입.
    count[nums[j]] -= 1  # 위치 인덱스 하나 깎음

print(sorted_nums)

 

3.  선택 정렬 (불안정 정렬)

 

 

 

cf. 2차원 리스트에서 하나 기준으로 잡았으면 나머지는 안정 정렬 해버린다.