정렬 : 데이터를 특정한 기준에 따라 순서대로 나열하는 것
insertion sort, selection sort, bubble sort, quick sort, merge sort, heap sort
1. Bubble sort
인접한 두 원소를 비교
왼쪽원소 > 오른쪽 원소 이면 swap
가장 큰 원소부터 오른쪽에 정렬
가장쉽지만 비효율적인 알고리즘
N개의 입력을 정렬하는 시간 복잡도 O(N^2)
자료의 교환은 이동 3번에 해당하는 작업,,
하나의 요소가 끝과 끝으로 이동하려면 배열의 모든 요소들과 교환되어야,,
특히 이미 정렬 완료된 배열에서도 회전 수행함
Advanced Bubble Sort
백준 2750번
2. Merge sort
분할정복 방식으로 설계됨
하나의 배열을 반으로 나누고 나뉜 배열들을 정렬, 다시 하나의 배열로 합침
**분할 정복: 한번에 해결못하는 문제를 작은 문제로 분할해서 해결하는 알고리즘
divide, conquer, combine
백준 11728번
백준 2751번
C++ 정렬함수: std::sort
인자로 배열의 처음시작위치랑 끝 위치를 보내준다
오름차순정렬이 디폴트(내림차순하고싶으면 세번째 인자에 greaer<>() 넣기)
세번째 인자에 비교함수(cmp)넣어서 원하는 조건대로 정렬 가능
<<??>>
1. 비교함수 작성 시 인자를 넘겨줄때 왜 const와 &를 사용할까
2. 정렬 알고리즘 중엔 시간 복잡도가 O(n)인 계수 정렬(Counting sort)가 있다
어떻게?? 그리고 왜 계수 정렬 안쓸끼
3. 정렬 알고리즘은 stable sort랑 unstable sort로 나눌수 있는데,, 각각이 무엇일까
4. 자료형이 pair<int,int>인 배열을 comp 없이 정렬하면 어떻게 될까
백준 11651번
백준 1758번
백준 1431번
백준 1946번
백준 1026번