728x90 정렬4 계수 정렬(Counting Sort) 이때까지 배운 O(N log N)의 시간복잡도인 선택, 버블, 삽입 정렬 그리고 O(N^2)의 시간복잡도인 퀵, 병합, 힙 정렬을 배웠습니다. 가장 빨랐던 정렬은 아무래도 퀵정렬이었는데요. 이거보다 빠르게 정렬을 하는 계수 정렬에 대해 알아보겠습니다. 다음의 5 이하 자연수 데이터들을 오름차순 정렬하세요. 1 3 5 2 3 1 3 4 4 3 4 2 3 4 3 1 1 2 4 3 3 1 2 3 4 5 1 3 2 4 정렬할 데이터 개수가 30개입니다. 특징은 모든 데이터가 1부터 5 사이입니다. 계수 정렬은 이처럼 적절한 '범위 조건'이 있어야한다는 전제에서 굉장히 빠른 알고리즘입니다. 그 속도는 O(N) 입니다. ( 저도 처음보는 시간복잡도의 속도입니다.) 계수 정렬(Counting Sort)는 단순하게 '.. 2020. 6. 1. C++ Sort() 사용 클래스 객체를 이용해서 정렬하는 건 실무에서 많이 사용되는 방법이고 프로그래밍 대회에선 실행 시간에 안 좋은 측면 때문에 자주 사용되지 않는다고 합니다. 실제로는 C++에 vector 라이브러리에, pair 를 더 많이 이용합니다. 정렬은 이미 만들어진 훌륭한 라이브러리가 많으니깐 원리를 이해하고 바로 라이브러리를 사용하면 좋겠죠! sort 함수는 라이브러리에 포함되어있고 pair는 라이브러리에 포함되어 있습니다. #include #include using namespace std; //sort 기준을 스스로 정할 수 있음 //단순 데이터 정렬 기법은 현실적이지 않음 bool compare(int a,int b){ return a < b; } int main(void){ int a[10] = {9, 3,.. 2020. 5. 30. 삽입정렬 복습(Insertion Sort) 오늘은 삽입정렬에 대해 또 알아보았습니다. 삽입정렬은 O(N^2)의 정렬 알고리즘 중에서도 가장 효율적인 알고리즘입니다. 특히 정렬이 되어있을때 가장 효과적입니다. 삽입정렬의 핵심은 '삽입을 하고자하는 원소 앞에 배열이 이미 정렬되어진 상태라고 가정' 하는 겁니다. 그러고 삽입하고자 하는 원소를 그 정렬된 배열 앞으로 삽입합니다. 예를 들어보겠습니다. 5 3 4 2 1 이라는 배열이 존재합니다. 첫번째 원소를 선택합니다. 5는 첫번째 원소이기 때문에 이미 정렬이 되어있습니다. 그럼 두번째 원소 3을 보겠습니다. 3이 들어갈 수 있는 두 곳이 있습니다. _5_ 3 4 2 1 여기서 3은 5보다 작이 때문에 앞 쪽 공간에 삽입됩니다. 3 5 4 2 1 다음원소인 4의 들어갈 장소를 모색합니다. _3_5_4 .. 2020. 5. 27. 버블 정렬 복습(Bubble Sort) 오늘은 버블 정렬에 대해 배워 보았습니다. 분명 1,2 학년때 다 한건데 3학년이 된 지금에서야 다시 복습을 하는게 바보같다는 생각이 들 때도 있지만 지금이라도 열심히 해야지라는 생각이 듭니다. 버블 정렬은 O(N^2) 인 세개의 정렬(선택,버블,삽입) 중에서도 가장 비효율적인 정렬입니다. 버블정렬은 무조건 옆에 요소와 비교하고 교환합니다. 여기서 무조건 교환을 하기 때문에 알고리즘의 비효율적인 부분이 커집니다. 애를 들어 설명해보겠습니다. 3 1 4 5 2 라는 배열이 존재합니다. 첫번째 첫번째 3 을 옆에 요소 1과 비교 합니다. 1이 더 크기 때문에 교환합니다. 1 3 4 5 2 그리고 두번째 수 3을 다시 4와 비교한 후 크면 교환합니다. 여기선 4보다 작기 때문에 교환을 하지는 않습니다. 1 3.. 2020. 5. 27. 이전 1 다음 728x90
