ÃÑ ÆäÀÌÁö ¼ö : 3224
![]()
|
Facebook Joinc ±×·ì
Joinc QA »çÀÌÆ®
![]()
Tweet
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À» ±âÀÔÇϸé, ´ñ±ÛÀÌ ¸ÞÀÏ·Î Àü´ÞµË´Ï´Ù. |
|