sort

1. 데이터 처리를 용이하게 하기 위해 함

insertion sort

1. 두번째 원소부터 끝 원소까지 해당 원소의 적절한 위치 찾은 후 삽입 --> 배열 앞에서 부터 해당 해당 원소까지 정렬 됨
   1. ex) 정렬된 카드가 있을 경우 새로운 카드를 가지고 와서 그 카드 위치 찾는 방식
2. 과정(반복)
   1. 현 위치보다 앞쪽에서 자신보다 큰 값을 뒤로 이동,
   2. 더 이상 큰 값이 없거나 맨 앞 위치에 도달하면 그곳에 원소 넣음

bubble sort

1. 범위 만큼 인접한 원소 비교 후 교환 --> 최댓값이 배열 뒤에서부터 정렬
2. 과정(반복)
   1. 인접한 두 원소 비교 --> 앞쪽이 크면 교환
   2. 범위 1씩 감소

selection sort

1. 대상 범위에서 가장 작은 값 찾아 --> 첫 원소와 교환
2. 과정
   1. 대상 범위에서 가장 작은 값 찾기
   2. 대상 범위 첫 원소와 교환

--> O(NlogN)

quick sort

1. pivot 기준으로 작으면 앞으로, 크면 뒤로 이동(partitioning) --> 반복(recursion)
2. 과정
   1. 첫 원소 pivot --> 큰 원소는 뒤로, 작은 원소는 앞으로 이동
   2. 앞 부분과 뒷부분 다시 quick sort 반복

heap sort

1. heap 상태에서 첫 원소와 끝 원소 위치 교환 --> size 1 감소 후 adjust 하고 반복
2. 과정
   1. 초기 heap 구성
   2. 다음 (n-1)회 반복
      1. heap 에서 첫원소와 끝원소 위치 교환
      2. heap의 size 1감소
      3. root 기준으로 adjust(reheaping)

merge sort

1. 정렬된 2개의 배열을 하나의 배열로 합치는 과정
2. 과정: 길이 1부터 시작하여 길이를 2배씩 증가하며 s만큼의 길이끼리 merge
   1. merge_sort: s를 2배씩 증가시키며 pass 콜
   2. merge_pass: 2개씩 merge 함수 콜 && 나머지 처리
   3. merge: 리스트 2개 merge

radix sort

1. 여러 key에 대하여 sort
2. key의 종류에 우선순위
3. 종류
   1. msd(most siginificant digit) sort
   2. lsd(least siginificant digit) sort

step1

step2

step3

library qsort

1. qsort(list, n, size, comp)
   1. n: 개수
   2. size: 단위 크기
   3. comp: 사용자 정의 함수
      1. void* 로 받음 --> 어떤 타입이든 casting 해주기 위해서

   int compare(const void* a, const void* b)
   {
     int *p1 = (int *) a; 
     int *p2 = (int *) b;
     if (*p1 == *p2) 
     	return 0;
     if (*p1 < *p2) 
     	return -1;
     if (*p1 > *p2) 
     	return 1;
   }