이코테 정렬

선택 정렬 

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

index = 0 부터 시작해서 가장 작은 원소를 찾아내어 0부터 9순으로 선택하여 정렬한다.

가장 작은 데이터를 선택해 맨앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 두 번째 데이터와 바꾸는 과정.

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
 
val br = BufferedReader(InputStreamReader(System.`in`))
 
fun main()= with(br){
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    val arr = mutableListOf<Int>(7,5,9,0,3,1,6,2,4,8)
   bw.write("$arr")    bw.write("\n")
    var min_index = 0
    var temp = 0
    for(i in 0 until arr.size){
        min_index = i
        for(k in i+1 until arr.size){
            if(arr[min_index]>arr[k]){
                min_index = k
            }
        }
        temp = arr[i]
        arr[i]=arr[min_index]
        arr[min_index]=temp
    }
    bw.write("$arr")
    bw.flush()
    bw.close()
}

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
 
val br = BufferedReader(InputStreamReader(System.`in`))
 
fun main() = with(br){
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    val arr = mutableListOf<Int>(7,5,9,0,3,1,6,2,4,8)
    bw.write("$arr")
    bw.write("\n")
    var temp = 0
    for(i in 1 until arr.size){
        for(j in i downTo 1){
            if(arr[j]<arr[j-1]){
                temp = arr[j-1]
                arr[j-1]=arr[j]
                arr[j]=temp
            }
            else
                break
        }
    }
    bw.write("$arr")
    bw.flush()
    bw.close()
}
 

 

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
 
val br = BufferedReader(InputStreamReader(System.`in`))
val arr = mutableListOf<Int>(5,7,9,0,3,1,6,2,4,8)
 
fun main() = with(br){
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    bw.write("$arr")
    bw.write("\n")
    bw.flush()
    quick(0,arr.size-1)
    bw.write("$arr")
    bw.write("\n")
    bw.flush()
    bw.close()
}
 
fun quick(start:Int,end:Int){
    var temp = 0
    if(start>=end)
        return
    var pivot = start
    var left = start+1
    var right = end
    while(left<=right){
        while(left<=end && arr[left]<=arr[pivot])
            left+=1
        while(start<right && arr[right]>=arr[pivot])
            right-=1
        if(left>right) {
            temp = arr[pivot]
            arr[pivot]=arr[right]
            arr[right]=temp
        }
        else{
            temp = arr[left]
            arr[left]=arr[right]
            arr[right]=temp
        }
    }
    quick(start,right-1)
    quick(right+1,end)
}
 

계수정렬 

데이터 갯수가 제한적인 학생들의 성적 정렬같은 종류에 유리함.

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
 
val br = BufferedReader(InputStreamReader(System.`in`))
 
 
fun main() = with(br){
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    val arr = mutableListOf<Int>(7,5,9,0,3,1,6,2,9,1,4,8,0,5,2)
    val count_arr = MutableList(10,{0})
    bw.write("$arr ")
    bw.write("\n")
    for(i in 0 until arr.size){
        count_arr[arr[i]]+=1
    }
    for(i in 0 until count_arr.size){
        for(k in 0 until count_arr[i]){
            bw.write("$i ")
        }
    }
    //[7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
    // 0 0 1 1 2 2 3 4 5 5 6 7 8 9 9
    bw.flush()
    bw.close()
}
 
 

 

 

정렬 속도 비교 

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
 
val br = BufferedReader(InputStreamReader(System.`in`))
 
fun main() = with(br)
{
    var arr = MutableList(5000,{0})
    for (i in 0 until 5000){
        arr[i]=i
    }
    var arr2 = MutableList(5000,{0})
    for (i in 0 until 5000){
        arr2[i]=i
    }
    var arr3 = MutableList(5000,{0})
    for (i in 0 until 5000){
        arr3[i]=i
    }
    var bw = BufferedWriter(OutputStreamWriter(System.out))
   // bw.write("$arr")
   // bw.write("\n")
    var temp = 0
    var start = System.nanoTime()
    for(i in 1 until arr.size){
        for(j in i downTo 1){
            if(arr[j]<arr[j-1]){
                temp = arr[j-1]
                arr[j-1]=arr[j]
                arr[j]=temp
            }
            else
                break
        }
    }
    var end = System.nanoTime()
    System.out.println("선택 정렬 수행시간: " + (end - start).toString() + " ns")
  //  bw.write("$arr")
  //  bw.write("\n")
    bw.flush()
  //  bw.write("$arr2")
   // bw.write("\n")
    start = System.nanoTime()
    quick(arr2,0,arr2.size-1)
    end = System.nanoTime()
    System.out.println("퀵 정렬 수행시간: " + (end - start).toString() + " ns")
 //   bw.write("$arr2")
  //  bw.write("\n")
    bw.flush()
 
    //bw.write("$arr3")
    //bw.write("\n")
    start = System.nanoTime()
    arr3.sort()
    end = System.nanoTime()
    System.out.println("라이브러리 정렬 수행시간: " + (end - start).toString() + " ns")
   // bw.write("$arr3")
   // bw.write("\n")
    bw.flush()
    bw.close()
}
 
fun quick(arr2:MutableList<Int>,start:Int,end:Int){
    var temp = 0
    if(start>=end)
        return
    var pivot = start
    var left = start+1
    var right = end
    while(left<=right){
        while(left<=end && arr2[left]<=arr2[pivot])
            left+=1
        while(start<right && arr2[right]>=arr2[pivot])
            right-=1
        if(left>right) {
            temp = arr2[pivot]
            arr2[pivot]=arr2[right]
            arr2[right]=temp
        }
        else{
            temp = arr2[left]
            arr2[left]=arr2[right]
            arr2[right]=temp
        }
    }
    quick(arr2,start,right-1)
    quick(arr2,right+1,end)
}

이미 정렬된 상태의 배열을 정렬하는 경우

선택정렬은 매우 좋은 퍼포먼스를 보여주고

퀵 정렬은 정신을 못차리고,

라이브러리는 어느정도 선방하는 모습이다.

정렬이 되지않은 상태에서는

퀵정렬이 나은 퍼포먼스를 보여줄꺼라고 생각했지만 아니였다.

 

그냥 라이브러리 소트 쓰자.