º»¹®/³»¿ë
1. ¼±ÅÃÁ¤·ÄÀÇ °³³ä°ú Ư¡
¼±ÅÃÁ¤·Ä(Selection Sort)Àº Á¤·ÄµÇÁö ¾ÊÀº ¸®½ºÆ®¿¡¼ °¡Àå ÀÛÀº(¶Ç´Â °¡Àå Å«) ¿ä¼Ò¸¦ ã¾Æ ¸Ç ¾ÕÀÇ ¿ä¼Ò¿Í ±³È¯ÇÏ´Â °úÁ¤À» ¹Ýº¹ÇÏ¿© Àüü¸¦ Á¤·ÄÇÏ´Â ¾Ë°í¸®ÁòÀÌ´Ù. Áï, ù ¹øÂ° ·çÇÁ¿¡¼´Â ¸®½ºÆ® Àüü¿¡¼ °¡Àå ÀÛÀº °ªÀ» ã¾Æ ù ¹øÂ° ÀÚ¸®¿Í ¹Ù²Ù°í, µÎ ¹øÂ° ·çÇÁ¿¡¼´Â µÎ ¹øÂ° ÀÌÈÄÀÇ ¸®½ºÆ®¿¡¼ °¡Àå ÀÛÀº °ªÀ» ã¾Æ µÎ ¹øÂ° ÀÚ¸®¿Í ¹Ù²Ù´Â ½ÄÀ¸·Î ÁøÇàµÈ´Ù.
ÀÌ ¾Ë°í¸®ÁòÀÇ °¡Àå Å« Ư¡Àº ±³È¯ Ƚ¼ö°¡ Àû´Ù´Â °ÍÀÌ´Ù. °¢ ·çÇÁ¸¶´Ù ÇÑ ¹øÀÇ ±³È¯¸¸ ¼öÇàµÇ±â ¶§¹®¿¡, ±³È¯ ºñ¿ëÀÌ ³ôÀº °æ¿ì¿¡´Â À¯¸®ÇÒ ¼ö ÀÖ´Ù. ±×·¯³ª ±×¿¡ ¹ÝÇØ ºñ±³ Ƚ¼ö´Â »ó´çÈ÷ ¸¹¾Æ, ÀüüÀûÀ¸·Î È¿À²ÀÌ ³·Àº ÆíÀÌ´Ù. ½Ã°£º¹Àâµµ´Â ÃÖ¼±, Æò±Õ, ÃÖ¾Ç ¸ðµÎ O(n©÷)ÀÌ´Ù.
¼±ÅÃÁ¤·ÄÀº ±¸ÇöÀÌ °£´ÜÇϰí, Ãß°¡ÀûÀÎ ¸Þ¸ð¸®¸¦ »ç¿ëÇÏÁö ¾Ê´Â(in-place) Á¤·ÄÀ̶ó´Â ÀåÁ¡ÀÌ ÀÖÁö¸¸, ÀÔ·Â µ¥ÀÌÅͰ¡ ÀÌ¹Ì Á¤·ÄµÇ¾î À־ Ç×»ó µ¿ÀÏÇÑ ºñ±³ Ƚ¼ö¸¦ °¡Áö¹Ç·Î ºñÈ¿À²ÀûÀÌ´Ù.
2. »ðÀÔÁ¤·ÄÀÇ °³³ä°ú Ư¡
»ðÀÔÁ¤·Ä(Insertion Sort)Àº ¸» ±×´ë·Î ¸®½ºÆ®ÀÇ °¢ ¿ä¼Ò¸¦ `»ðÀÔ`ÇÏ¸é¼ Á¤·ÄÇÏ´Â ¹æ½ÄÀÌ´Ù. µÎ ¹øÂ° ¿ä¼ÒºÎÅÍ ½ÃÀÛÇØ¼, ¾ÕÀÇ ¿ä¼Òµé°ú ºñ±³Çϸç ÀÚ½ÅÀÇ À§Ä¡¡¦(»ý·«)