정렬

• 버블 정렬

• 인접한 원소끼리의 비교

  • O(n^2)

     

    # [27,35,12,3,4,56,42] > 27부터 시작해서 가장큰 56이 맨뒤에 안착
    a= [27,35,12,3,4,56,42]
     
    for i in range( len(a)-1 ):    #6번 비교
        for j in range( len(a)-i-1 ):  #뒤에가 점점 차서 비교횟수가 줄어든다. 처음에 6번비교! 그다음 5번!
            if a[j]>a[j+1]:
                a[j+1],a[j]= a[j], a[j+1]
     
    print(a)

 

 

• 카운팅 정렬

• 정렬할값이 양의 정수이고 자료의 범위를 알고있을때

• O(n+k)

  ex) 1000명의 학생들의 시험 점수 0~100점

  +최대값이 적당히 작을때

  이유? [1,2,3,4, 10000000] 이면 중간과정이 되게 불필요

a= [1,2,2,0,3,3,6,4,3,5]    #데이터
b= [0,0,0,0,0,0,0]          #빈배열 (6까지 있으므로 7칸!)
c= [1,1,2,3,1,1,1]          #각 자리수마다 카운트값 (1은 1개니깐 1의자리에 '1' )
d= [1,2,4,7,8,9,10]         #C에서 처음자리부터 차례로 더해줌
e= [0,0,0,0,0,0,0,0,0,0]    #답
#이제 데이터를 끝에서 부터 찾는다.
# 5 [1,2,4,7,8,9,10] => [1,2,4,7,8,8,10] => [ , , , , , , , ,5, ]
# 3 [1,2,4,7,8,9,10] => [1,2,4,6,8,8,10] => [ , , , , , ,3, ,5, ]
#                    => [0,1,2,4,7,8, 9] => [0,1,2,2,3,3,3,4,5,6]
 
for i in range(len(a)):
    b[a[i]] += 1    # 1의값이면 1의 자리 +1  [c를 만들어가는 과정]
for i in range(0,len(b)-1):
    b[i+1] += b[i]    # [d를 만들어가는 과정]
for i in range (len(a)-1,-1,-1):    # a의 끝에서 부터 확인을 시작한다. (a 9번째 자리 == '5') 
    e[b[a[i]]-1] = a[i]             # e[b[5]-1] = 5 // b[5]-1는 5의 자리를 의미한다.
    b[a[i]] -= 1                    # b[5] = b[5] -1 을 함으로써 5의 카운트 값을 1 낮춘다 
    
# e 에는 값이 저장된다.

 

 

 

• 셀렉션 정렬
• 리스트의 최소값을 찾아서 맨앞에 놓는다.
• O(n^2)

# [23,6,3,56,33,23,4,2]
for i in range(0,len(a)-1):    # 23기준!
    min = i
    for j in range(i+1,len(a)-1): # 6부터 비교하기 시작한다.
        if a[min]>a[j]:    # 6이 더작으니 최소값의 index는 6의 인덱스인 '1'로 변경! 
            min = j
    a[i],a[min] = a[min],a[i] # 결국 j는 2의 인덱스인 '7' 맨 앞자리와 바꾼다!
    
    # 앞자리는 채워졌으니 i=1 부터시작해서 6기준! 시작