알고리즘 개념14 삽입 정렬(insertion sort) 삽입 정렬적절한 위치에 삽입한다.버블 정렬, 선택 정렬보다 빠르다.삽입 정렬은 옆의 값과 비교해서 더 클 때만 스위칭하기 때문에 더 빠르다.특정한 경우에 굉장히 빠르게 작용할 수 있다. ( 예 : 거의 정렬되어 있는 데이터일 때 ) 시간 복잡도 => O(N^2) 동작 원리- 특정한 위치에서 앞의 원소들과 비교해서 적당한 위치에 들어간다.ex) 1 5 6 7 8 10 4 3 2 9 => 4가 적절한 위치에 들어갈 때 이미 앞 부분은 다 정렬이 되어 있기 때문에 4만 앞의 원소들과 하나씩 비교해가며 들어가면 되기 때문에 매번 비교할 때마다 선택이나 버블처럼 교환하지 않아도 된다. 1 5 6 7 8 4 10 3 2 9 -> 4와 8 비교해서 자리 바꿈 .. 2022. 2. 8. 퀵정렬(Quick Sort) 퀵 정렬데이터의 갯수가 적을 때는 괜찮지만 데이터의 갯수가 10만 개만 넘어가도 보통의 상황에서선택,버블,삽입 정렬 알고리즘을 사용하기가 힘들다. 이런 경우 퀵 정렬을 사용한다면아무리 많은 양의 데이터라도 빠르게 정렬을 할 수 있다.대표적인 분할 정복 알고리즘c 라이브러리로 제공하는 sort() 함수가 퀵 정렬을 기반으로 구현되어 있다.이미 정렬이 되어있거나 거의 정렬되어 있는 데이터에 사용할 때는 성능이 매우 떨어짐 퀵 정렬의 시간 복잡도평균 : O(N * logN) -> 반씩 쪼개서 정렬하기 떄문에 logN인 것이다.최악 : O(N^2) 퀵 정렬이 최악인 경우에도 O(N * logN)을 보장하는 방법- STL 라이브러리에서 제공하는 sort() 함수는 퀵 정렬을 기반으로 하되 별도의 처리.. 2022. 2. 7. 이전 1 2 3 다음
