[알고리즘/Python] 삽입정렬 | Insertion sort
삽입정렬 [ Insertion sort ] - 배열의 인덱스를 늘려가면서 원소가 들어가야할 자리를 찾아서 삽입하는 정렬 -정렬 완료 된 부분 - 자리를 찾아야하는 원소 1 [34, 24, 67, 43, 93] 2 [24, 34, 67, 43, 93] 3 [24, 34, 67, 43, 93] 4 [24, 34, 43, 67, 93] 시간복잡도 ⏱ 최선의 경우 : O(n) 이미 정렬이 다 되어있는 경우 최악의 경우 : O(n²) 평균 : O(n²) 장점 1. 거의 정렬되어 있는 상태 ( O(n) ) 면 매우 빠른 효율성을 가지고 잇다 단점 1. 최악의 경우 ( ex : 거꾸로 정렬되어 있는 경우 ) O(n²) 라는 시간복잡도를 갖게 된다. 2. 데이터의 상태와 크기에 따라성능의 편차가 심하다 [ python..
2020. 10. 6.
[알고리즘/Python] 선택정렬 | selection sort
선택정렬 [ selection sort ] - 전체원소 중에 가장 작은 값을 가장 앞에 있는 원소와 바꾸고, 바꾼 원소를 제외하고 계속 가장 작은 값을 앞으로 보내는 정렬 패스 테이블 최솟값 0 [9, 1, 6, 8, 5, 4, 2, 0] 0 1 [0, 1, 6, 8, 5, 4, 2, 9] 1 3 [0, 1, 2, 8, 5, 4, 6, 9] 2 4 [0, 1, 2, 8, 5, 4, 6, 9] 4 5 [0, 1, 2, 4, 5, 8, 6, 9] 5 6 [0, 1, 2, 4, 5, 8, 6, 9] 6 7 [0, 1, 2, 4, 5, 6, 8, 9] 8 시간복잡도 ⏱ 최선의 경우 : O(n²) 최악의 경우 : O(n²) 평균 : O(n²) 장점 1. 구현이 쉬움2. 정렬을 위한 비교 횟수는 많지만 실제로 교환..
2020. 10. 6.
