거품정렬 Bobble Sort / 선택정렬 Selection sort

거품정렬

 

파이썬예제

import unittest

def bubblesort(alist):
    for i in range(len(alist)-1):
        for j in range(len(alist)-1):
            if alist[j] > alist[j+1]:
                alist[j], alist[j+1] = alist[j+1], alist[j]
    return alist


class unit_test(unittest.TestCase):
    def test(self):
        self.assertEqual([1, 2, 3, 4, 5, 6], bubblesort([4, 6, 1, 3, 5, 2]))
        self.assertEqual([1, 2, 3, 4, 5, 6], bubblesort([6, 4, 3, 1, 2, 5]))
        self.assertEqual([1, 2, 3, 4, 5, 6], bubblesort([6, 5, 4, 3, 2, 1]))

 

https://www.youtube.com/watch?v=gfjIKgAjiB8&list=PLVNY1HnUlO25sSWDr7CzVvkOF3bUgkiQQ&index=3 

 

선택정렬

하나의 공간이 필요하다. minimunValue

import unittest

def selectionSort(input):
    for i in range(len(input) - 1):
        # assume the min is the first element
        idx_min = i
        j = i + 1

        # test against elements after i to find the smallest
        while j < len(input):
            if(input[j] < input[idx_min]):
                # found new minimum; remember its index
                idx_min = j
            j = j + 1

        if idx_min is not i:
            # swap
            input[idx_min], input[i] = input[i], input[idx_min]

    return input

class unit_test(unittest.TestCase):
    def test(self):
        self.assertEqual([1, 2, 3, 4, 5, 6], selectionSort([4, 6, 1, 3, 5, 2]))
        self.assertEqual([1, 2, 3, 4, 5, 6], selectionSort([6, 4, 3, 1, 2, 5]))
        self.assertEqual([1, 2, 3, 4, 5, 6], selectionSort([6, 5, 4, 3, 2, 1]))

https://www.youtube.com/watch?v=_MoTnAW6fs8&list=PLVNY1HnUlO25sSWDr7CzVvkOF3bUgkiQQ&index=4