import random

def binary_search(data, search):
    if len(data) == 1 and search == data[0]:
        return True
    elif len(data) == 1 and search != data[0]:
        return False
    elif len(data) == 0:
        return False

    index = len(data)//2
    find = data[index]
    if search == find:
        return True
    else: 
        if search < find:
            return binary_search(data[:index], search)
        elif search > find:
            return binary_search(data[index+1:],search)

data = random.sample(range(100), 5)
search = random.sample(range(100), 1)
print(binary_search(sorted(data), search[0]))

병합을 하기 위해서 먼저 주어진 숫자 리스트를 작은 단위로 쪼개 주어야 한다.

def split(data):
    if len(data) <= 1:
        return data

    medium = int(len(data)/2)
    left = split(data[:medium])
    right = split(data[medium:])

    return merge(left, right)

가장 작은 단위(길이가 1인 리스트)로 쪼개진 리스트를 비교하여 병합해 주면서 순서를 맞춰가게 된다.

def merge(left, right):
    result = list()
    left_point, right_point = 0, 0
    while len(left) > left_point and len(right) > right_point: 
        if left[left_point] < right[right_point]:
            result.append(left[left_point])
            left_point += 1
        else:
            result.append(right[right_point])
            right_point += 1

    while len(left) > left_point:
         result.append(left[left_point])
         left_point += 1

    while len(right) > right_point:
        result.append(right[right_point])
        right_point += 1

    return result

전체 코드는 아래와 같다.

import random
def split(data):
    if len(data) <= 1:
        return data

    medium = int(len(data)/2)
    left = split(data[:medium])
    right = split(data[medium:])

    return merge(left, right)

def merge(left, right):
    result = list()
    left_point, right_point = 0, 0
    while len(left) > left_point and len(right) > right_point: 
        if left[left_point] < right[right_point]:
            result.append(left[left_point])
            left_point += 1
        else:
            result.append(right[right_point])
            right_point += 1

    while len(left) > left_point:
         result.append(left[left_point])
         left_point += 1

    while len(right) > right_point:
        result.append(right[right_point])
        right_point += 1

    return result


data = random.sample(range(100), 5)
print(split(data))

1. 기준값을 정한다.

    pivot = data[0]

2. 기준값보다 작은 원소는 기준값의 왼쪽에 배치한다.

    left = list()
    for number in range(1, len(data)):
        if number < pivot:
            left.append(number)

3. 기준값보다 큰 원소는 기준값의 오른쪽에 배치한다.

    right = list()
    for number in range(1, len(data)):
        if number >= pivot:
            right.append(number)

4. 위의 과정들을 반복하여 정렬을 완성한다.

    def quick_sort1(data):
        if len(data) <= 1:
            return data
        pivot = data[0]
        left,right = list(), list()
        for i in range(1, len(data)):
            if pivot >= data[i]:
                 left.append(data[i])
            else:
                 right.append(data[i])
        return quick_sort1(left) + [pivot] + quick_sort1(right)

또 다른 방법으로 구현 가능하다.

def quick_sort2(data):
    if len(data) <= 1:
        return data
    pivot = data[0]
    left = [number for number in data[1:] if number < pivot]
    right = [number for number in data[1:] if number >= pivot]
    return quick_sort2(left) + [pivot] + quick_sort2(right)

1. Factorial

    def factorial1(n):
        if n > 1:
            return n*factorial(n-1)
        return n
   
    def factorial2(n):
        if n == 1:
            return n
        return n*factorial2(n-1)
   

2. Palindrome

    def palindrome(sentence):
        if len(sentence) <= 1:
            return True
   
        if sen[0] == sentence[-1]:
            return palindrome(sentence[1:-1])
        else : 
            return False

1. 정렬이 안된 배열의 두번째 원소를 바로 앞 원소와 비교한다. 더 작은 원소가 앞에 위치하도록 위치를 바꿔준다. [70, 31, 3, 72, 20] -> [31, 70, 3, 72, 20]

   if data[j] < data[j-1]:
       data[j], data[j-1] = data[j-1], data[j]

2. 자신보다 큰 원소를 찾기 전까지 위의 과정을 반복한다.

   for j in range(i, 0, -1):
       if data[j] < data[j-1]:
           data[j], data[j-1] = data[j-1], data[j]
       else:
           break

3. 정렬이 안된 배열의 원소를 차례대로 1번과 2번 과정을 반복한다. [31, 70, 3, 72, 20] -> [31, 3, 70, 72, 20]

   [31, 3, 70, 72, 20] -> [3, 31, 70, 72, 20]

   [3, 31, 70, 72, 20] -> [3, 31, 70, 20, 72]

   [3, 31, 70, 20, 72] -> [3, 31, 20, 70, 72]

   def insert(data):
       for i in range(1, len(data)):
           for j in range(i, 0, -1):
               if data[j] < data[j-1]:
                   data[j], data[j-1] = data[j-1], data[j]
               else:
                   break
       return data

1. 정렬이 되지 않은 배열에서 가장 작은 수를 선택한다. [70, 31, 3, 72, 20]

    index = 0
    for j in range(len(data)):
        if data[index] > data[j] :
            index = j

2. 가장 작은 수로 선택 된 원소와 정렬되지 않은 배열의 가장 왼쪽 원소를 교환한다. [70, 31, 3, 72, 20] --> [ 3, 31, 70, 72, 20]

    index = 0
    for j in range(len(data)):
        if data[index] > data[j] :
            index = j
    data[0], data[index] = data[index], data[0]

3. 위의 1번 2번 과정을 정렬이 될 때까지 반복한다. [70, 31, 3, 72, 20] --> [ 3, 31, 70, 72, 20]

   [ 3, 31, 70, 72, 20] --> [ 3, 20, 70, 72, 31]

   [ 3, 20, 70, 72, 31] --> [ 3, 20, 31, 72, 70]

   [ 3, 20, 31, 72, 70] --> [ 3, 20, 31, 70, 72]

    def select(data):
        for i in range(len(data)-1):
            index = i
            for j in range(i+1, len(data)):
                if data[index] > data[j]:
                    index = j
            if i != index:
                data[i], data[index] = data[index], data[i]
        return data

다양한 정렬 알고리즘 중 버블 정렬에 대해 정리해보고자 한다.

버블 정렬은 인접한 앞뒤 원소를 비교하여 앞에 있는 원소의 크기가 뒤에 있는 원소의 크기보다 더 클 경우 두 원소의 위치를 교환한다.

1. 앞뒤 원소를 비교하여 앞에 있는 원소의 크기가 뒤에 있는 원소의 크기보다 더 클 경우 두 원소의 위치를 교환한다. [70, 31, 3, 72, 20] -> [31, 70, 3, 72, 20]

   if data[i] > data[i+1]:
      data[i], data[i+1] = data[i+1], data[i]

2. 가장 큰 원소가 배열의 가장 오른쪽에 위치하도록 1번의 과정을 반복한다. [70, 31, 3, 72, 20] -> [31, 70, 3, 72, 20]

   [31, 70, 3, 72, 20] -> [31, 3, 70, 72, 20]

   [31, 3, 70, 72, 20] -> [31, 3, 70, 20, 72]

   for i in range(len(data) - 1):
      # 1번 코드 
      if data[i] > data[i+1]:
          data[i], data[i+1] = data[i+1], data[i]

3. 위의 1번 2번 과정을 모든 원소들이 정렬 될 때까지 반복한다.

    for j in range(len(data) - 1):
        # 2번 코드
        for i in range(len(data) - 1):
          # 1번 코드 
          if data[i] > data[i+1]:
              data[i], data[i+1] = data[i+1], data[i]

   4. 최적화 단계, 2번 과정이 끝나면 가장 큰 원소가 가장 오른쪽에 위치하기 때문에 마지막 원소는 비교할 필요가 없다. 또한, 이미 정렬이 완료 되었을 경우 반복문을 종료한다.

      def bubblesort(data):
      # 3번 코드
      for j in range(len(data) - 1):
          # 최적화
          swap = False
          # 2번 코드, 최적화 len(data) - j - 1
          for i in range(len(data) - j - 1):
              # 1번 코드 
              if data[i] > data[i+1]:
                  data[i], data[i+1] = data[i+1], data[i]
                  swap = True
          if not swap:
              break
      return data
      

   ```

삶에 대한 생각과 업무에 대한 나의 태도를 돌아보게 되었고, 많은 시도를 통해 성장을 하였다. 나는 그전의 내가 많이 낯설다.

새로운 마음으로, 블로그 플랫폼을 이전하였다. 개인적인 목표는 github에 나만의 블로그를 만드는 것인데, 우선 당장 글을 쓰는 습관을 기르는 것이 목표이기에 미디엄과 깃허브 블로그, velog 중 velog를 택하게 되었다. (티스토리 블로그는 이미 있다) 미디엄은 정기 구독으로 글을 읽을만큼 나의 관심사에 대한 글이 많은 플랫폼이지만, velog의 디자인이 나에게 더 매력적이라 느껴져 그냥 선택했다. 물론 간편한 사용 방법과 가독성 또한 뛰어난 것 같다. 아마도, front-end에 대해 더 관심이 가게 되면, github로 이전하지 않을까 싶다.

과거의 나는 블로그 플랫폼에 관한 모든 글을 읽고 서로의 장단점을 분석하고, 결국 고민고민하다 플랫폼을 선택하면 아이디를 수천번 고민하다 결국 지쳐 '글은 내일부터 써야지..' 했겠지만 "우선 시작하자"라는 생각들이 내 삶에 가져온 긍정적인 변화들 덕분에 이 블로드 또한 우선 시작하게 되었다. (실제로 정확히 1년전 위의 일을 반복하다 새로운 블로그 개설을 포기했다)