Sorting

Sorting

Bubble Sort

Code

for i in range(n):
  for j in range(i+1,n):
    if data[j-1]<data[j]:
      data[j-1],data[j]=data[j],data[j-1]

Insertion Sort

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

Selection Sort

for i in range(n)
    min_value=data[i]
    min_index=i
    for j in range(i,n):
      if data[j]<min_value:
        min_value=data[j]
        min_index=j
    data[i],data[min_index]=data[min_index],data[i]

Quick Sort

def quick_Sort(n,data,start,end):
  if n<=1:
    return data
  pivot=data[0]
  temp=data[1:]

  left=[x for x in temp if x <= pivot]
  right=[x for x in temp if x > pivot]

  return quick_Sort(len(left),left,0,len(left)-1) + [pivot]+ quick_Sort(len(right),right,0,len(right)-1)

Merge Sort

def merge_Sort(data):
  if len(data)<=1:
    return data
  mid=len(data)//2

  left=merge_Sort(data[:mid])
  right=merge_Sort(data[mid:])
  return merge(left,right)
  
def merge(left,right):
  i,j=0,0
  temp=[]
  while i<len(left) and j<len(right):
    if left[i] <= right[j]:
      temp.append(left[i])
      i+=1
    else:
      temp.append(right[j])
      j+=1

  while i<len(left):
    temp.append(left[i])  
    i+=1

  while j<len(right):
    temp.append(right[j])
    j+=1

Question Types

주로 정렬을 직접적으로 다루는 문제는 많이는 없으나, 보통 정렬은 다른 문제를 해결하기 위한 기본 알고리즘을 많이 활용된다.