728x90 정렬3 [Algorithm] Bubble Sort : 버블 정렬, 버블 소트 ( 코드 포함 ) 선택정렬과 마찬가지로 가장 큰 원소를 끝의 자리로 옮기는 작업을 반복하는 정렬이다. 단, 끝의 자리로 보내는 방법이 다르다. 비교하면서 더 큰 숫자를 오른쪽으로 계속 보내게 되는데 이 결과 가장 큰 수가 가장 오른쪽에 간다. 버블정렬의 수행시간(시간복잡도)은 O(n²)이다. 따라서 숫자가 적을 때만 사용하자. [프로그래밍 공부]/Algorithm 2022. 1. 22. 더보기 ›› [Algorithm] Merge Sort : 병합 정렬, 병합 소트 ( 코드 포함 ) 입력된 배열의 중간지점을 찾은 뒤 반으로 나눈다. 그리고 나눈 전반부와 후반부를 각각 독립적으로 정렬한다 ( 재귀적으로 다시 반으로 정렬 ) 마지막으로 전반부와 후반부를 병합한다. 병합정렬의 수행시간은 평균 O(n*log n)이고 최악의 경우에도 O(n * log n) 이다. 코드 이전까지 정렬함수와 다르게 정렬하고자 하는 부분의 시작인덱스와 끝 인덱스를 넣는다. 재귀적으로 되어있는데 merge는 분열되어 각각 정렬된 배열을 하나로 합치는 역할을 한다. merge함수 결과 [프로그래밍 공부]/Algorithm 2022. 1. 22. 더보기 ›› [Algorithm] Quick Sort : 퀵 정렬, 퀵 소트 ( 코드 포함 ) 퀵 정렬은 평균적으로 O(n logN) 시간이 소요되며 좋은 성능을 가진다. 맨 뒤의 원소를 기준으로 삼고 맨 뒤의 원소보다 작은 것은 기준 앞에, 큰 것은 기준 뒤에 놓는다. 기준의 양 옆을 재귀적으로 반복한다. 10 4 5 2 1 6 3 9 8 7 이 배열 안에 있으면 최초 7을 기준으로 좌우 정렬한다 따라서 4 5 2 1 6 3 7 10 9 8 이 되며 기준의 양 옆을 다시 재귀적으로 동작시키면 4 5 2 1 3 을 다시 재정렬하여 2 1 3 4 5 가 된다 이를 다시 기준의 양 옆을 재 정렬하면 1 2 3 4 5 가 된다. [프로그래밍 공부]/Algorithm 2021. 12. 11. 더보기 ›› 728x90 이전 1 다음
