정렬 알고리즘 정리

이제 코딩 짬좀 찼지 하고 야심차게 백준에 들어갔다가 바로 정렬에 뜌땨이가 되어버렸다…
간단하기도 하니 쉬운 정렬은 어느정도 이해를 해 놓아야 겠다.

학교 자료구조 시간에 배운 간단한 정렬들만 적어둔다.

선택 정렬

정렬안된 곳에서 최소값 선택, 정렬 최우측과 교환.

• 정렬x 부분 어디에 최소값이 있든 한번 다 뒤져야함 (뒤에 어디에 최소값이 있을줄 알고!) » 입력에 민감하지 않음(O(n^2))

삽입 정렬

정렬 안된 곳 최 좌측 (정렬부분 뒤 부터 비교해)정렬 부 삽입

• 이미 정렬된 배열 정렬시 교환 없이 한번씩만 비교. (O(n))
• 입력 역순 정렬 시 최악의 경우 O(n^2) 비교 필요.
• 따라서 입력에 민감함.
• 거의 정렬된 입력, 정렬된 파일에 소량의 신규데이터 추가 경우에 사용 시 유리함.

• 합병, 퀵 정렬 과 달리 보통 반복문으로 구현 > 이론적은 몰라도 실질적 빠름.

• 삽입정렬 시 삽입부분 구현

  1. 내가한 방식 : 정렬된곳에서, 삽입할 위치를 찾아서, 삽입

     삽입할 위치를 저장해둬야해 불편, 결국 삽입한 위치만큼 원소를 밀어줘야해서 교환횟수도 후의 경우와 같음.

1. 모범 : 정렬된 곳 끝에서부터 차례대로 비교하며 교환, 정렬된 부분이 더이상 더 크지 않으면 교환을 멈춤.

내가 과연 정렬을 잘 구현할 수 있는가는 백준의 2750번에서 해보도록하자.

버블 솔트