자료구조 | 정렬 Sorting | 숙명여대 학점교류

숙명여대 학점교류로 듣는 자료구조

day 10. 2022.1.4. 화요일

---

정렬

selection sort

bubble sort

insertion sort

quick sort

heap sort

merge sort

radix sort

---

sorting이란 무엇인가..

* preliminary stage for searching

* formulation

- a list of record (R0, R1, ..., Rn-1)

: Ri = key(Ki) + other data (구조체 같은 형태)

- sorting problem

: to search a permutation (R0, R1, ..., Rn-1) that satisfies Ki < Ki+1 (0 <= i <=n-1)

 

sorting의 유형

• internal sort

performed in main memory for a small list

• external sort

partition a large data into multiple segment

sort each segment in main memory

merge segments using external storage

 

performance evaluation of sorting algorithms

# of comparisions of key values

# of data movements

---

internal sort

selection sort

bubble sort

insertion sort

quick sort

heap sort

merge sort

radix sort

---

selection sort

6.8. The Selection Sort — Problem Solving with Algorithms and Data Structures (runestone.academy)

선택 정렬

<min> 방식, <max> 방식이 있다.

n <= 1, already sorted. so, assume n>1

move the smallest/largest element to the left/right end of the list

recursively sort the remaining n-1 elements a[1:n-1]

complexity : O(n^2)

// n for min/max find n times

 

* problem

sort a set of unsorted elements (U) (n>1)

* algorithm

- find and move the smallest/largest element of U to a sorted list (S)

- repeat this procedure whild there is any remaining element in U

for i in range(n):
	from list[i] thru list[n-1]:
    	find and mark the smallest item by list[min]
   	swap list[i] with list[min]

* code ( min version )

class SelectionSort:
    def __init__(self, num):
        self.num = num
        self.size = len(num)
        print("Selection Sort", self.num)
    def __str__(self):
        for i in range(self.size):
            print("%2d " % self.num[i])
    def sort(self):
        n = self.size
        for i in range(n-1):
            min = i
            for j in range(i+1, n):
                if self.num[j] < self.num[min]: min = j
            self.num[i], self.num[min] = self.num[min], self.num[i]
            print(self.num)

num = [31, 9, 10, 23, 49, 15, 11, 7]
s = SelectionSort(num)
s.sort()

=> 단계별 출력 내용 알아야한다

---

bubble sort

* bubble sort algorithm

assume n>1

compare a[i] with a[i+1] for 0<=i<=n-2

if a[i] > a[i+1], then swap a[i] with a[i+1]

each pass moves the largest key to the end of list

repeat this with the ramaining n-1 elements a[0:n-2]

if swap does not occur on the previous pass, sort is completed

 

* time complexity : O(n^2)

 

* python implementation

class Bubblesort:
    def __init__(self, num):
        self.num = num
        self.size = len(num)
        print("bubble sort", self.num)
    def __str__(self):
        for i in range(self.size):
            print("%2d " % self.num[i])
    def swap(self, a, b):
        self.num[a], self.num[b] = self.num[b], self.num[a]
    def sort(self):
        n = self.size
        for i in range(n-1):
            flag = 0
            for j in range(0, n-i-1):
                if self.num[j] > self.num[j+1]:
                    self.swap(j, j+1)
                    flag = 1
            if flag == 0: break
            print(self.num)

num = [13,25,9,12,34,52,49,17,5,8]
s = Bubblesort(num)
s.sort()

output

bubble sort [13, 25, 9, 12, 34, 52, 49, 17, 5, 8]
[13, 9, 12, 25, 34, 49, 17, 5, 8, 52]
[9, 12, 13, 25, 34, 17, 5, 8, 49, 52]
[9, 12, 13, 25, 17, 5, 8, 34, 49, 52]
[9, 12, 13, 17, 5, 8, 25, 34, 49, 52]
[9, 12, 13, 5, 8, 17, 25, 34, 49, 52]
[9, 12, 5, 8, 13, 17, 25, 34, 49, 52]
[9, 5, 8, 12, 13, 17, 25, 34, 49, 52]
[5, 8, 9, 12, 13, 17, 25, 34, 49, 52]