전체 글 썸네일형 리스트형 Quick Sort 🌲 Quick Sort by Hoare (1962) Strategy Choose a pivot item randomly Partition into 2 subarrays Sort each subarray recursively Ex 15 22 13 27 12 10 20 25 15 : pivot item 1. partition 10 13 12 15 22 27 20 25 remember pivot's position 2. Sort subarrays recursively 10 12 13 15 20 22 25 27 procedure quicksort (low, high, index); var pivotpoint : index; begin if high > low then { partition(low, high, p.. 더보기 Binary search 🎲 Binary search Task Assume that we have n ≥ 1 distinct integers that are already sorted and stored in the array list For a given integer m, we want to know whether there is 1 such that list[i] = m Input : a sorted array list[i], 0 ≤ i < n, an integer m Output: i if list[i] = m, -1 if there is no such i Specification let left = 0, rigth = n - 1, middle = (left + rigth) / 2 1. If m < list[middle].. 더보기 Selection sort Selection sort Task : From those integers that are currently unsorted, find the smallest and place it next in the sorted list Input: n integers are stored in an array list[i], 0 ≤ i < n Output: a sorted list[i], 0 ≤ i < n Specification for (i = 0; i < n; i++){ Examine list[i] to list[n-1] and supposed that the smallest integer is at list[min]; Interchange list[i] and list[min]; } 정렬이 안 돼있는 숫자들 중.. 더보기 이전 1 ··· 76 77 78 79 다음