[イコタ]配列

• 선택 정렬은 기본 정렬 라이브러리나 뒤에서 다룰 알고리즘에 비해서 매우 비효율적. 그러나 특정한 리스트에서 가장 작은 데이터를 찾는 일이 코딩 테스트에서 잦으므로 형태는 알아두어야 함.

삽입 정렬(insertion sort)

데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입하면 어떨까?!

• 삽입 정렬은 선택 정렬에 비해 실행 시간 측면에서 더 효율적인 알고리즘

• 필요할 때만 위치를 바꾸므로 '데이터가 거의 정렬 되어 있을 때' 훨씬 효율적

• 선택 정렬은 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 바꾸는 반면 삽입 정렬은 그렇지 않다.

• 삽입 정렬은 특정한 데이터를 적절한 위치에 "삽입" 한다는 의미에서 "삽입 정렬"

• 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다.

• 정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤에, 그 위치에 삽입된다는 점이 특징

• 삽입 정렬은 두번째 데이터 부터 시작한다. 왜냐하면 첫 번째 데이터는 그 자체로 정렬되어 있다고 판단하기 때문이다.

• 삽입 정렬의 특징으로는 정렬이 이루어진 원소는 항상 오름차순을 유지하고 있다는 점이다.

-> 이러한 특징 때문에 삽입 정렬에서는 특정한 데이터가 삽입될 위치를 선정할 때(삽입할 위치를 찾기 위하여 한 칸씩 이동할 때),삽입될 데이터보다 작은 데이터를 만나면 그 위치에서 멈추면 된다.

#삽입 정렬

array = [7,5,9,0,3,1,6,2,4,8]

for i in range(1, len(array)) :
  for j in range(i, 0, -1): # 인덱스 i부터 1까지 감소하며 반복하는 문법
    if array[j] < array[j -1]:  #한 칸씩 왼쪽으로 이동
        array[j], array[j -1] = array[j -1], array[j]
    else: #  자기보다 작은 데이터를 만나면 그 위치에서 멈춤
      break
print(array)

#퀵 정렬

array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]


def quick_sort(array, start, end) :
  if start >= end: #원소가 1개인 경우 종료
    return
  pivot = start
  left = start + 1
  right = end
  while left <= right:
    #피벗보다 큰 데이터를 찾을 때까지 반복
    while left <= end and array[left] <= array[pivot]:
      left += 1

    #피벗보다 작은 데이터를 찾을 때까지 반복
    while right > start and array[right] >= array[pivot]:
      right -= 1

    if left > right: #엇갈렸다면 작은 데이터와 피벗을 교체
      array[right], array[pivot] = array[pivot], array[right]
    
    else: # 엇갈리지 않았다면 작은 데이터와 피벗을 교체
      array[left], array[right] = array[right], array[left]

    #분할 이후 왼쪽과 오른쪽 부분에서 각각 정렬 수행

  quick_sort(array, start, right - 1)
  quick_sort(array, right +1, end)



quick_sort(array, 0, len(array)-1)
print(array)</code></pre>

#퀵 소트,시간 면에서는 비효율

array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]


def quick_sort(array):
  # 리스트가 하나 이하의 원소만을 담고 있다면 종료
  if len(array) &lt;= 1:
    return array

  pivot = array[0] #피벗은 첫 번째 원소
  tail = array[1:] # 피벗을 제외한 리스트 


  left_side = [x for x in tail if x &lt;= pivot] #분할된 왼쪽 부분
  right_side = [x for x in tail if x &gt;= pivot] #분할된 오른쪽 부분




  #분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬을 수행하고, 전체 리스트를 반환 
  return quick_sort(left_side) + [pivot] + quick_sort(right_side)

print(quick_sort(array))

array = [7,5,9,0,3,1,6,2,9,1,4,8,0,5,2]

#모든 범위를 포함하는 리스트 선언(모든 값은 0으로 초기화)

print(max(array))

count = [0] * (max(array) + 1)


for i in range(len(array)) :
  count[array[i]] += 1 # 각 데이터에 해당하는 인덱스의 값 증가


for i in range(len(count)): # 리스트에 기록된 정렬 정보 확인
  for j in range(count[i]):
    print(i, end =' ') # 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

result_1 = sorted(array #sorted 함수

array.sort() # sort함수 별도의 정렬된 리스트가 반환되지 않고, 내부 원소가 바로 정렬

print(result_1)
print("------------")
print(array)


array_1 = [("바나나", 2), ("사과", 5), ("당근", 3)]

def setting(data):
  return data[1]

result = sorted(array_1, key = setting)
print(result)

#N을 입력받기

n = int(input())

#N개의 정수를 입력받아 리스트에 저장

array = []
for i in range(n):
  array.append(int(input()))

array = sorted(array, reverse = True)

for i in array:
  print(i, end = " ")</code></pre>
<h2 id="성적이-낮은-순서로-학생-출력하기">성적이 낮은 순서로 학생 출력하기</h2>
<pre class=" language-null"><code class=" language-null">#N을 입력받기
n = int(input())


#N명의 학생 정보를 입력받아 리스트에 자장
array = []
for i in range(n):
  input_data = input().split()
  #이름은 문자열 그대로, 점수는 정수형으로 변환하여 저장
  array.append((input_data[0], int(input_data[1])))


#키(key)를 용하여, 점수를 기준으로 정렬
array = sorted(array, key = lambda student: student[1])

#정렬이 수행된 결과를 출력
for student in array:
  print(student[0], end = '')

n, k = map(int, input().split())

# N과 K를 입력받기
a = list(map(int, input().split())) #배열 A의 모든  원소를 입력받기
b = list(map(int, input().split())) #배열 B의 모든 원소를 입력받기

a.sort() #배열 A는 오름차순 정렬 수행
b.sort(reverse = True) #배열 B는 내림차순 정렬 수행


for i in range(k):
  #A의 원소가 B의 원소보다 작은 경우
  if a[i] < b[i]:
    # 두 원소를 교체
    a[i], b[i] = b[i], a[i]
  else: # A의 원소가 B의 원소보다 크거나 같을 때, 반복문을 탈출
    break   



print(sum(a)) #배열 A의 모든 원소의 합을 출력