1) 힙이란? 힙이라는 데이터 구조를 사용하여 정렬하는데, 최소값이나 최대값을 찾는데 최적화되어있는 완전이진트리 형태의 자료구조이다. 2) 힙의 시간복잡도 삽입정렬에서는 각 라운드의 첫 숫자를 그 왼쪽에 있는 숫자와 비교한다. 만약 왼쪽에 있는 숫자가 작다면 교체가 발생하지 않고 라운드를 종료한다. 하지만 꺼낸 숫자가 정렬 완료 영역의 숫자보다 작을 때는 그 숫자가 가장 왼쪽에 도착할 때까지 비교와 교체 작업을 한다. k라운드에서는 k-1회씩 작업한다. 따라서 최악의 경우에는 2라운드에서 1회, 3라운드에서 2회, ..., n라운드에서 n-1회의 비교와 교체가 발생하므로 계산 시간이 버블 정렬이나 선택 정렬과 같이 O(n^2)이다. 그리고 최악의 입력 데이터는 마찬가지로 역순으로 나열된 경우이다. 3) ..

1) 삽입정렬이란? 왼쪽부터 순서대로 정렬하는 방식으로 좌측에는 정렬이 끝난 숫자가 오게 되고 우측에는 아직 확인하지 않은 숫자가 남게됨 우측의 미탐색 영역엣 숫자를 하나 꺼내서 정렬이 끝난 영역의 적절한 위치에 삽입해 나가는 방식 2) 삽입정렬의 시간복잡도 삽입정렬에서는 각 라운드의 첫 숫자를 그 왼쪽에 있는 숫자와 비교한다. 만약 왼쪽에 있는 숫자가 작다면 교체가 발생하지 않고 라운드를 종료한다. 하지만 꺼낸 숫자가 정렬 완료 영역의 숫자보다 작을 때는 그 숫자가 가장 왼쪽에 도착할 때까지 비교와 교체 작업을 한다. k라운드에서는 k-1회씩 작업한다. 따라서 최악의 경우에는 2라운드에서 1회, 3라운드에서 2회, ..., n라운드에서 n-1회의 비교와 교체가 발생하므로 계산 시간이 버블 정렬이나 선택..

1) 버블정렬이란? 오른쪽부터 왼쪽 방향으로 인접한 두 개의 숫자를 비교해서 교환 오른쪽부터 왼쪽으로 숫자를 옮겨가는 모양이 물속에서 거품이 올라오는 모양과 비슷하다고 해서 버블이라고 함 2) 버블정렬의 시간복잡도 버블 정렬은 선형 탐색을 위해 1라운드에서 n-1, 2라운드에서 n-2, ... , n-1라운드에서 1회 비교를 한다. 따라서 비교 횟수는 (n-1) + (n-2) + ... + 1 ≈ n^/2가 된다. 비교 횟수는 입력 데이터의 순서와 상관없이 일정하다. 또한, 숫자 교체횟수는 입력 데이터에 의존한다. 입력 데이터가 작은 순으로 나열되어 있다면 교체는 발생하지 않는다. 하지만 큰 데이터가 큰 순으로 나열되어 있다면 비교할 때마다 교체해야한다. 따라서 선택 정렬의 계산 시간은 O(n^2)이다...

1) 선택정렬이란? 수열 중에서 최솟값을 검색해서 왼쪽 끝에 있는 숫자와 교체하는 작업 반복 2) 선택정렬의 시간복잡도 선택 정렬은 선형 탐색을 위해 1라운드에서 n-1, 2라운드에서 n-2, ... , n-1라운드에서 1회 비교를 한다. 따라서 비교 횟수는 (n-1) + (n-2) + ... + 1 ≈ n^/2 ps. 버블 정렬과 같다 또한, 숫자 교체는 각 라운드에서 최대 1회이며, 입력 데이터가 작은 순으로 나열되어 있다면 교체는 발생하지 않는다. 따라서 선택 정렬의 계산 시간은 O(n^2)이다. 3) 선택정렬 구현 #include int main(void){ int data[6] = {5, 2, 4, 6, 1, 3}; int temp; printf("Before sorting :\n"); for(..