<div id="readability-page-1" class="page"><div><h2 id="버블정렬">버블정렬</h2>
<h3 id="아이디어">아이디어</h3>
<blockquote>
인접한 원소들끼리 교환 * N-1번 반복 (N: 배열의 길이)
</blockquote>
한번 반복할 때마다 한 자리씩 확정되는 정렬이기 때문에, 
교환해야하는 원소 수가 하나씩 줄어들고 <code>(j)</code> 
N-1개의 원소를 정렬하면 <code>(i)</code> 나머지 한자리는 자동으로 정렬된다.
<h3 id="구현">구현</h3>
<pre><code>def bubble_sort(arr):
 for i in range(len(arr)-1): # 반복 횟수
 for j in range(len(arr)-1): # 교환하는 원소 수
 if arr[j] &gt; arr[j + 1]:
 arr[j], arr[j + 1] = arr[j + 1], arr[j]</code></pre>
<h2 id="선택정렬">선택정렬</h2>
<h3 id="아이디어-1">아이디어</h3>
<blockquote>
원소 하나씩 선택 (N-1번) * 최소값을 찾아서 교환
</blockquote>
매번 교환할 필요 없이 인덱스만 넘겨주고, 최소원소의 인덱스를 구한 후 한번만 직접 교환하면 된다. 
버블 정렬과 마찬가지로 한번 반복할 때마다 한 자리씩 확정되는 정렬이다.
<h3 id="구현-1">구현</h3>
<pre><code>def selection_sort(arr):
 for i in range(len(arr)-1):
 min_idx=i
 for j in range(i+1,len(arr)):
 if arr[i] &gt; arr[j]:
 min_idx=i
 arr[min_idx],arr[i]=arr[i],arr[min_idx]</code></pre>
<h2 id="삽입정렬">삽입정렬</h2>
<h3 id="아이디어-2">아이디어</h3>
<blockquote>
2번째 원소부터 앞 원소들과 비교하며 자기 자리를 찾아가는 정렬
</blockquote>
앞 원소들 중 더 작은 값 발견시 그 자리 바로 뒤에 삽입. 
그 자리를 포함한 이후 원소들은 뒤로 한칸씩 밀려나고, 
제자리를 찾은 원소는 원래 위치에서 삭제.
<h3 id="구현-2">구현</h3>
<pre><code>def insertion_sort(arr):
 for i in range(1,len(arr)):
 j=i-1
 while (j&gt;=0 and arr[i]&lt;arr[j]):
 j-=1
 arr.insert((j+1),arr[i])
 del arr[i+1]</code></pre>
(따라서, 삽입 삭제를 안하고 원소를 한칸씩 뒤로 밀어넣다가 
더 작은 값이 나오면 밀지 않고 빈자리에 쏙 넣어도 된다)
<pre><code>def insertion_sort(arr):
 for i in range(1, len(arr)):
 elem = arr[i]
 j = i
 while j &gt; 0 and arr[j - 1] &gt; elem:
 arr[j] = arr[j - 1]
 j -= 1
 arr[j] = elem</code></pre>
<h2 id="병합정렬">병합정렬</h2>
<h3 id="아이디어-3">아이디어</h3>
<blockquote>
정렬된 배열을 만드는 방법은, 두 개의 정렬된 배열을 합쳐 하나의 정렬된 배열을 만드는 것이다. <del>(그럼 그 두개의 정렬된 배열은?)</del>
</blockquote>
원소 2개 이상을 가지는 배열을 쪼개다 보면 원소 1개의 배열이 나온다. 
원소 1개 배열 2개를 <code>병합</code> -&gt; 원소 2개의 정렬된 배열 
2개 + 1개 or 2개+2개 <code>병합</code> -&gt; 원소 3개 or 4개의 정렬된 배열 
-&gt; 확장 
<ol>
<li>어떻게 쪼갤 것인가 </li>
<li>어떻게 합칠 것인가 </li>
</ol>
두가지 아이디어가 필요하다.
<h3 id="구현-3">구현</h3>
<pre><code>def merge_sort(arr):
 #둘로 쪼개고 하나로 합쳐라
 def sort(low, high):
 if high - low &lt; 2:
 return
 mid = (low + high) // 2
 sort(low, mid)
 sort(mid, high)
 merge(low, mid, high)

 def merge(low, mid, high):
 temp = []
 l, h = low, mid

 # low/high가 둘다 남아있을 때
 while l &lt; mid and h &lt; high:
 if arr[l] &lt; arr[h]:
 temp.append(arr[l])
 l += 1
 else:
 temp.append(arr[h])
 h += 1
 # low 또는 high만 남아있을 때
 while l &lt; mid:
 temp.append(arr[l])
 l += 1
 while h &lt; high:
 temp.append(arr[h])
 h += 1

 for i in range(low, high):
 arr[i] = temp[i - low]

 return sort(0, len(arr))</code></pre>
<h2 id="퀵소트퀵정렬">퀵소트(퀵정렬)</h2>
<h3 id="아이디어-4">아이디어</h3>
<blockquote>
원소 하나를 선택(PIVOT)하여 작은 원소들은 왼쪽으로, 큰 원소들은 오른쪽으로 위치하게 교환 <del>(그러면 이제 그 두 그룹을 다시...)</del>
</blockquote>
한번 정렬할 때마다 PIVOT으로 선택한 원소의 위치가 정해진다. 
PIVOT 값에 따라 두 구간으로 나뉘기 때문에 중간값에 가까울 수록 이상적인 정렬이 된다. 
<ol>
<li>어떻게 PIVOT을 선택할 것인가 </li>
<li>어떻게 큰값/작은값 으로 분리할 것인가 </li>
</ol>
두가지 아이디어가 필요하다.
<h3 id="구현-4">구현</h3>
<pre><code>def quick_sort(arr):
 def sort(low, high):
 if high &lt;= low:
 return

 mid = partition(low, high)
 sort(low, mid - 1)
 sort(mid, high)

 def partition(low, high):
 pivot = arr[(low + high) // 2]
 while low &lt;= high:
 while arr[low] &lt; pivot:
 low += 1
 while arr[high] &gt; pivot:
 high -= 1
 if low &lt;= high:
 arr[low], arr[high] = arr[high], arr[low]
 low, high = low + 1, high - 1
 return low

 return sort(0, len(arr) - 1)</code></pre>
<blockquote>
참고 
<a href="https://www.daleseo.com/sort-quick/">https://www.daleseo.com/sort-quick/</a> 
<a href="https://www.daleseo.com/sort-merge/">https://www.daleseo.com/sort-merge/</a>
</blockquote></div></div>

yeseolee.log

버블정렬
아이디어
인접한 원소들끼리 교환 * N-1번 반복 (N: 배열의 길이)
한번 반복할 때마다 한 자리씩 확정되는 정렬이기 때문에, 
교환해야하는 원소 수가 하나씩 줄어들고 (j) 
N-1개의 원소를 정렬하면 (i) 나머지 한자리는 자동으로 정렬된다.
구현
def bubble_sort(arr):
 for i in range(len(arr)-1): # 반복 횟수
 for j in range(len(arr)-1): # 교환하는 원소 수
 if arr[j] > arr[j + 1]:
 arr[j], arr[j + 1] = arr[j + 1], arr[j]
선택정렬
아이디어
원소 하나씩 선택 (N-1번) * 최소값을 찾아서 교환
매번 교환할 필요 없이 인덱스만 넘겨주고, 최소원소의 인덱스를 구한 후 한번만 직접 교환하면 된다.
버블 정렬과 마찬가지로 한번 반복할 때마다 한 자리씩 확정되는 정렬이다.
구현
def selection_sort(arr):
 for i in range(len(arr)-1):
 min_idx=i
 for j in range(i+1,len(arr)):
 if arr[i] > arr[j]:
 min_idx=i
 arr[min_idx],arr[i]=arr[i],arr[min_idx]
삽입정렬
아이디어
2번째 원소부터 앞 원소들과 비교하며 자기 자리를 찾아가는 정렬
앞 원소들 중 더 작은 값 발견시 그 자리 바로 뒤에 삽입.
그 자리를 포함한 이후 원소들은 뒤로 한칸씩 밀려나고,
제자리를 찾은 원소는 원래 위치에서 삭제.
구현
def insertion_sort(arr):
 for i in range(1,len(arr)):
 j=i-1
 while (j>=0 and arr[i]<arr[j]):
 j-=1
 arr.insert((j+1),arr[i])
 del arr[i+1]
(따라서, 삽입 삭제를 안하고 원소를 한칸씩 뒤로 밀어넣다가 
더 작은 값이 나오면 밀지 않고 빈자리에 쏙 넣어도 된다)
def insertion_sort(arr):
 for i in range(1, len(arr)):
 elem = arr[i]
 j = i
 while j > 0 and arr[j - 1] > elem:
 arr[j] = arr[j - 1]
 j -= 1
 arr[j] = elem
병합정렬
아이디어
정렬된 배열을 만드는 방법은, 두 개의 정렬된 배열을 합쳐 하나의 정렬된 배열을 만드는 것이다. (그럼 그 두개의 정렬된 배열은?)
원소 2개 이상을 가지는 배열을 쪼개다 보면 원소 1개의 배열이 나온다.
원소 1개 배열 2개를 병합 -> 원소 2개의 정렬된 배열
2개 + 1개 or 2개+2개 병합 -> 원소 3개 or 4개의 정렬된 배열
-> 확장 
어떻게 쪼갤 것인가 
어떻게 합칠 것인가 
두가지 아이디어가 필요하다.
구현
def merge_sort(arr):
 #둘로 쪼개고 하나로 합쳐라
 def sort(low, high):
 if high - low < 2:
 return
 mid = (low + high) // 2
 sort(low, mid)
 sort(mid, high)
 merge(low, mid, high)
 def merge(low, mid, high):
 temp = []
 l, h = low, mid
 # low/high가 둘다 남아있을 때
 while l < mid and h < high:
 if arr[l] < arr[h]:
 temp.append(arr[l])
 l += 1
 else:
 temp.append(arr[h])
 h += 1
 # low 또는 high만 남아있을 때
 while l < mid:
 temp.append(arr[l])
 l += 1
 while h < high:
 temp.append(arr[h])
 h += 1
 for i in range(low, high):
 arr[i] = temp[i - low]
 return sort(0, len(arr))
퀵소트(퀵정렬)
아이디어
원소 하나를 선택(PIVOT)하여 작은 원소들은 왼쪽으로, 큰 원소들은 오른쪽으로 위치하게 교환 (그러면 이제 그 두 그룹을 다시...)
한번 정렬할 때마다 PIVOT으로 선택한 원소의 위치가 정해진다.
PIVOT 값에 따라 두 구간으로 나뉘기 때문에 중간값에 가까울 수록 이상적인 정렬이 된다. 
어떻게 PIVOT을 선택할 것인가 
*어떻게 큰값/작은값 으로 분리할 * 것인가 
두가지 아이디어가 필요하다.
구현
def quick_sort(arr):
 def sort(low, high):
 if high <= low:
 return
 mid = partition(low, high)
 sort(low, mid - 1)
 sort(mid, high)
 def partition(low, high):
 pivot = arr[(low + high) // 2]
 while low <= high:
 while arr[low] < pivot:
 low += 1
 while arr[high] > pivot:
 high -= 1
 if low <= high:
 arr[low], arr[high] = arr[high], arr[low]
 low, high = low + 1, high - 1
 return low
 return sort(0, len(arr) - 1)
참고
https://www.daleseo.com/sort-quick/
https://www.daleseo.com/sort-merge/

[Python] 정렬 정렬해보기

댓글