WIL 항해W4 자료구조/알고리즘 3주차

자료구조/알고리즘 3주차

 

항해를 시작한지 벌써 4주가 지난다.

 

이번주에는 힙, 버블소트, 선택정렬, 삽입정렬 등을 배웠다. 

 

지난 주말에 결혼식가느라 빠지고 주말동안 완전 놀았더니,

이번주 진도 따라잡기가 힘들었다. 

 

🔢 힙

힙은 데이터에서 최대값과 최소값을 빠르게 찾기 위해 만들어진 완전 이진 트리이다.

 

최대값 힙이면 

루트에 최대값이 있고, 모든 부모는 자식 노드의 값보다 항상 크다.

그러나 좌, 우 자식노드의 위치가 작은순서나, 큰 순서로 있는 것은 아닌다.

 

 

🔢 버블 소트

버블소트는 1번째 요소와 2번째 요소를, 2번째 요소와 3번째 요소를 ... 2개씩 오른쪽으로 이동하며 비교하면서, 자리를 교환하는 방식이다.

출처 : https://dev.to/buurzx/buble-sort-4jkc

오름차순의 경우에

작은 숫자, 큰 숫자 순서이면 그대로 놔두고, 

큰 숫자, 작은 숫자 순서이면 둘의 자리를 바꿔준다.

 

🔢 선택 정렬

선택 정렬은 요소를 쭉 보면서 가장 작은 요소를 맨 앞으로 옮기고,

또 나머지 요소 중에 가장 작은 요소를 찾아서 2번째 자리에 오게 한다.

선택 정렬을 직접 구현해보았는데,

처음에 구현한 코드는 최종 결과는 잘 나오길래 구현이 잘 되었나 했는데,

중간마다 print를 해보니 최소값을 찾으면서, 작은 애를 발견 할때마다 swap 해주었었다.

 

그래서 그 부분을 수정하여 코드를 완성하였다.

def select(lst):

    for i in range(len(lst)-1):
        minTemp = i  # 최소값을 찾기 위해 한번 도는 중에 최소값 index 임시저장
        
        for j in range(1, len(lst)-i):
            if lst[i] > lst[i+j] and lst[minTemp] > lst[i+j]: 
                minTemp = i+j
                
        lst[i], lst[minTemp] = lst[minTemp], lst[i]

    return lst