¼ÒÆ® ¾Ë°í¸®Áò - ¹öºí ¼ÒÆ®
ÃÑ ÆäÀÌÁö ¼ö : 3224

Àüü ÇÔ¼ö/¿ë¾î»çÀü
Facebook Joinc ±×·ì   Joinc QA »çÀÌÆ®



joinc´Â Firefox¿Í chrome¿¡¼­ Å×½ºÆ® Çß½À´Ï´Ù. IE¿¡¼­´Â Å×À̺íÀÌ ±úÁö°Å³ª À̹ÌÁö°¡ º¸ÀÌÁö ¾ÊÀ» ¼ö ÀÖ½À´Ï´Ù. ƯÈ÷ ±¸±Û DocsÀ̹ÌÁöÀÇ °æ¿ì ¿¢¹Úó¸®µÉ ¼ö ÀÖ½À´Ï´Ù.

¹öºí ¼ÒÆ®´Â ÀÎÁ¢¿ø¼Ò¸¦ ºñ±³Çؼ­ ´õ Å« ¿ø¼Ò¸¦ µÚ·Î º¸³»´Â ¹æ½ÄÀ» »ç¿ëÇÑ´Ù. º´ ¹Ø¹Ù´Ú¿¡¼­ »ý±ä ¹öºíÀÌ À§·Î ¿Ã¶ó¿À¸é¼­ Á¡Á¡ ´õ Ä¿Áö´Â °Í°ú ºñ½ÁÇϱ⠶§¹®¿¡ ¹öºí¼ÒÆ®¶ó°í ¸í¸íÇÏ°Ô µÇ¾ú´Ù.

¸Å¿ì °£´ÜÇÏ°Ô ±¸ÇöÇÒ ¼ö ÀÖÁö¸¸, ¸¹Àº °æ¿ì¿¡ À־ ¸Å¿ì ºñÈ¿À²ÀûÀ̶ó´Â ´ÜÁ¡À» °¡Áø´Ù.

¿¹¸¦µé¾î Äü¼ÒÆ®´Â Æò±Õ ½Ã°£º¹Àâµµ°¡ O(nlogn) Àε¥ ºñÇØ¼­ ¹öºí¼ÒÆ®´Â Ç×»ó O(n^2) À̶ó´Â ÃÖ¾ÇÀÇ ½Ã°£º¹Àâµµ¸¦ º¸¿©Áֱ⠶§¹®ÀÌ´Ù. - ¹°·Ð ¸î °¡Áö ¼öÁ¤»çÇ×À» Æ÷ÇÔ½ÃŰ¸é º¹Àâµµ¸¦ ÁÙÀÏ ¼ö ÀÖÁö¸¸ ¿¹¿Ü·Î ÇÑ´Ù -

Á¤·ÄÇØ¾ßÇÒ µ¥ÀÌÅÍÀÇ °¹¼ö°¡ ¸Å¿ì ÀûÀº °æ¿ì°¡ ¾Æ´Ï¶ó¸é Äü¼ÒÆ®°¡ »ç¿ëÇϱ⿡ °¡Àå ¹«³­ÇÑ ¼º´ÉÀ» º¸¿©ÁØ´Ù. ¿©·¯°¡Áö »óȲ¿¡ µû¸¥ ¼ÒÆ® ¾Ë°í¸®ÁòÀÇ ¼±Åÿ¡ ´ëÇØ¼­´Â µû·Î ¹®¼­¸¦ ÀÛ¼ºÇØ º¸µµ·Ï ÇϰڴÙ.

´ÙÀ½Àº Äü¼ÒÆ®°¡ ÀÌ·ç¾îÁö´Â °úÁ¤À» Visual ÇÏ°Ô º¸¿©ÁÖ°í ÀÖ´Ù.


´ÙÀ½Àº C¾ð¾î·Î ±¸ÇöµÈ Äü¼ÒÆ® ¾Ë°í¸®ÁòÀÌ´Ù.
#include <stdio.h> 
 
void b_sort(int data[], int size) 
{ 
    int tmp = 0; 
    int i, j; 
    int comparison = 0; 
    int swap = 0; 
 
    for (i = 0; i < size-1; i++) 
    { 
        for (j = 0; j < (size-1); j++) 
        { 
            comparison++; 
            if (data[j] > data[j+1]) 
            { 
                tmp = data[j+1]; 
                data[j+1] = data[j]; 
                data[j] = tmp; 
                swap++; 
            } 
        } 
    } 
    printf("Comparisons %d\n", comparison); 
    printf("Swap        %d\n", swap); 
} 
 
À§ÀÇ ÄÚµå´Â ¹öºí¼ÒÆ® ¾Ë°í¸®ÁòÀ» ±×´ë·Î Ç¥ÇöÇØÁÖ°í ÀÖÀ¸¸ç O(n^2)ÀÇ ½Ã°£º¹Àâµµ¸¦ º¸¿©ÁØ´Ù. ÀÌ ¹æ½ÄÀ¸·Î ÇÏÀÚ¸é ¿ÏÀüÈ÷ Á¤·ÄµÈ µ¥ÀÌÅÍÀÇ Á¤·Ä¿¡ ´ëÇØ¼­µµ O(n^2)ÀÇ ½Ã°£º¹Àâµµ¸¦ º¸¿©ÁØ´Ù. ´ÜÁö Swap°úÁ¤¸¸ÀÌ »ý·«µÉ »ÓÀÌ´Ù.

¿©±â¿¡ ¾à°£ÀÇ Á¶°ÇÀ» ÁÖ¸é ½Ã°£º¹Àâµµ¸¦ ÁÙÀÏ ¼ö ÀÖÀ¸¸ç, ¿ÏÀüÈ÷ Á¤·ÄµÈ µ¥ÀÌÅÍ¿¡ ´ëÇØ¼­´Â O(n)ÀÇ ½Ã°£º¹Àâµµ¸¦ °¡Áöµµ·Ï °³¼±ÇÒ ¼öµµ ÀÖ´Ù. ÈùÆ®¸¦ ÁÖÀÚ¸é swapÀÌ ÀϾ´ÂÁö¸¦ °Ë»çÇÏ´Â flag¸¦ µÖ¼­, swapÀÌ ÀϾÁö ¾Ê¾Ò´Ù¸é Á¤·ÄÀÌ ³¡³­°ÍÀ¸·Î ÆÇ´ÜÇÏ´Â °ÍÀÌ´Ù. ÀÌ ¹æ¹ýÀº Á÷Á¢ Å×½ºÆ®Çغ¸±â ¹Ù¶õ´Ù.
EmailÀ» ±âÀÔÇϸé, ´ñ±ÛÀÌ ¸ÞÀÏ·Î Àü´ÞµË´Ï´Ù.