برچسب ها: مرتب سازی بر اساس حباب Si، مرتب سازی حباب، مرتب سازی بر اساس حباب دو بعدی آرایه

مرتب سازی بر اساس حباب

و عمل الگوریتم بسیار ساده است. ما از طریق آرایه اعداد می رویم و سفارش را بررسی می کنیم (شماره بعدی باید بیشتر و برابر با قبلی باشد)، به محض اینکه آنها در معرض نقض سفارش قرار گرفتند، بلافاصله عناصر را در مکان ها مبادله می کنیم، ما به پایان می رسیم آرایه، و سپس ابتدا شروع کنید.

مرتب کردن آرایه (1، 5، 2، 7، 6، 3)
ما به ماسیف می رویم، شماره اول را بررسی می کنیم و دوم، آنها به ترتیب صعودی می روند. بعد، نقض سفارش وجود دارد، ما این عناصر را تغییر می دهیم
1, 2, 5, 7, 6, 3
ما همچنان از طریق آرایه ادامه می دهیم، 7 بیش از 5، اما 6 کمتر، بنابراین ما از مکان ها مبادله می کنیم
1, 2, 5, 6, 7, 3
3 نقض سفارش، تغییر مکان از 7
1, 2, 5, 6, 3, 7
ما به آغاز آرایه بازگشتیم و همین کار را انجام دهیم

1, 2, 5, 3, 6, 7
1, 2, 3, 5, 6, 7

گفته شده است که این شبیه به عناصر "شناور" بیشتر "ریه ها" مانند حباب ها است، به همین دلیل الگوریتم و چنین نامی دریافت می شود. void bubblesort (int * a، size_t size) (sype_t i، j؛ int tmp؛ برای (i \u003d 1؛ i< size; i++) { for (j = 1; j < size; j++) { if (a[j] > a) (tmp \u003d a [j]؛ a [j] \u003d a؛ a \u003d tmp؛))))

این الگوریتم همیشه (N-1) 2 مرحله را بدون در نظر گرفتن داده های ورودی انجام خواهد داد. حتی اگر آرایه مرتب شود، هنوز 2 بار (N-1) منتقل می شود. علاوه بر این، داده های مرتب شده در حال حاضر دوباره بررسی می شود.

اجازه دهید آن را مرتب سازی آرایه 1، 2، 4، 3

1 2 4 3
1 2 4 3
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4

پس از آن در مکان های عنصر تغییر یافت و نیازی به انتقال این بخش از آرایه بود. ما آن را به حساب و الگوریتم ادعا می کنیم

void bubblesort2 (int * a، size_t size) (size_t i، j؛ int tmp؛ برای (i \u003d 1؛ i< size; i++) { for (j = i; j > 0؛ j--) (اگر (a [j]< a) { tmp = a[j]; a[j] = a; a = tmp; } } } }

پیاده سازی دیگر

void bubblesort2b (int * a، size_t size) (sype_t i، j؛ int tmp؛ برای (I \u003d 1؛ I< size; i++) { for (j = 1; j <= size-i; j++) { if (a[j] < a) { tmp = a[j]; a[j] = a; a = tmp; } } } }

در این مورد، نیمه کمتری وجود خواهد داشت، اما هنوز هم مشکل مرتب سازی آرایه های مرتب شده در حال حاضر باقی مانده است: شما باید این کار را انجام دهید تا آرایه مرتب شده یک بار مشاهده شود. برای انجام این کار، به متغیر پرچم وارد کنید: اگر آرایه مرتب شود، آن را حذف می شود (پرچم \u003d 0). به محض این که ما به نقض نظم برویم، پرچم افزایش خواهد یافت (پرچم \u003d 1) و ما شروع به مرتب سازی آرایه به طور معمول.

void bubblesort3 (int * a، size_t size) (sype_t i؛ int tmp؛ char flag؛ انجام (پرچم \u003d 0؛ برای (I \u003d 1؛ I< size; i++) { if (a[i] < a) { tmp = a[i]; a[i] = a; a = tmp; flag = 1; } } } while (flag); }

در این مورد، پیچیدگی نیز در مورد n 2 است، اما در مورد یک آرایه مرتب شده، تنها یک پاساژ خواهد بود.

در حال حاضر الگوریتم را بهبود می بخشد. ما تابع فرم کلی را نوشتیم تا آرایه ای از نوع خالی را مرتب کنیم. از آنجا که نوع متغیر شناخته شده نیست، لازم است که اندازه یک عنصر آرایه و عملکرد مقایسه را انتقال دهید.

inttsort inttsort (const void * a، const void * b) (return * ((int *) a)\u003e * * (int *) b)؛) void bubblesort3g (void * a، size_t مورد، size_t size، int (* CMP) (Const Void *، Const Void *)) (sype_t i؛ void * tmp \u003d null؛ char flag؛ tmp \u003d malloc (item)؛ انجام دهید (flag \u003d 0؛ برای (I \u003d 1؛ I< size; i++) { if (cmp(((char*)a + i*item), ((char*)a + (i-1)*item))) { memcpy(tmp, ((char*)a + i*item), item); memcpy(((char*)a + i*item), ((char*)a + (i-1)*item), item); memcpy(((char*)a + (i-1)*item), tmp, item); flag = 1; } } } while (flag); free(tmp); }

تابع به نظر می رسد زشت - اغلب آدرس عنصر فعلی و قبلی محاسبه شده است. ما متغیرهای جداگانه ای را برای این موضوع برجسته می کنیم.

void bubblesort3gi void void * a، size_t item، size_t size، int (* cmp) (const void *، const void *)) (size_t i؛ void * tmp \u003d null؛ void * prev، cur؛ flag char؛ tmp \u003d Malloc (مورد)؛ انجام (پرچم \u003d 0؛ I \u003d 1؛ prev \u003d (char *) a؛ cur \u003d (char *) prev + item؛ در حالی که (من< size) { if (cmp(cur, prev)) { memcpy(tmp, prev, item); memcpy(prev, cur, item); memcpy(cur, tmp, item); flag = 1; } i++; prev = (char*)prev + item; cur = (char*)cur + item; } } while (flag); free(tmp); }

در حال حاضر با این توابع، شما می توانید آرایه های هر نوع را مرتب کنید، به عنوان مثال

void main () (int a \u003d (1، 0، 9، 8، 7، 6، 2، 3، 4، 5)؛ int i؛ bubblesort3gi (a، sizeof (int)، 10، intsort)؛ برای (i \u003d 0؛ من< 10; i++) { printf("%d ", a[i]); } _getch(); }

مرتب سازی آرایه چند بعدی

یک آرایه چند بعدی استاتیک اساسا از مرتب سازی یک بعدی متفاوت نیست. شما می توانید از اموال استفاده کنید که آرایه های یک بعدی و چند بعدی ای استاتیک در حافظه مشابهی دارند.

void main () (int a \u003d (1، 9، 2، 8، 3، 7، 4، 6، 5)؛ int i، j؛ bubblesort3gi (a، sizeof (int)، 9، intsort)؛ برای (i \u003d 0؛ من< 3; i++) { for (j = 0; j < 3; j++) { printf("%d ", a[i][j]); } } } Сортировка динамически созданного двумерного массива может быть произведена двумя способами. Во-первых, можно по определённому алгоритму находить индекс i-го и j-го элемента по порядковому номеру k от 0 до n * m. #include #عبارتند از. #عبارتند از. #عبارتند از. void bubblesort2d (int ** a، size_t m، sype_t n) (int tmp؛ size_t i، j، k، jp، ip؛ size_t size \u003d m * n؛ char flag؛ انجام (flag \u003d 0؛ برای (k \u003d 1 ؛ k< size; k++) { //Вычисляем индексы текущего элемента j = k / m; i = k - j*m; //Вычисляем индексы предыдущего элемента jp = (k-1) / m; ip = (k-1) - jp*m; if (a[i][j] > a) (tmp \u003d a [i] [j]؛ a [i] [j] \u003d a؛ a \u003d tmp؛ پرچم \u003d 1؛))) در حالی که (پرچم)؛ ) #define size_x 3 #define size_y 4 void main () (int ** a \u003d null؛ int i، j؛ a \u003d (int **) malloc (sizeof (int *) * size_x)؛ برای (I \u003d 0؛ من.< SIZE_X; i++) { a[i] = (int*) malloc(sizeof(int) * SIZE_Y); for (j = 0; j < SIZE_Y; j++) { a[i][j] = rand(); printf("%8d ", a[i][j]); } printf("\n"); } printf("\nafter sort\n"); bubbleSort2d(a, SIZE_X, SIZE_Y); for (i = 0; i < SIZE_X; i++) { for (j = 0; j < SIZE_Y; j++) { printf("%8d ", a[i][j]); } printf("\n"); } for (i = 0; i < SIZE_X; i++) { free(a[i]); } free(a); _getch(); }

ثانیا، ابتدا می توانید آرایه را به یک بعدی انتقال دهید، آرایه ی یک بعدی را مرتب کنید، سپس آن را به دو بعدی منتقل کنید.

void bubblesort3gi2d void void ** a، size_t مورد، size_t m، size_t n، int (* cmp) (const void *، const void *)) (size_t size \u003d m * n، sub_size \u003d n * مورد؛ size_t i، j ، k؛ void * arr \u003d malloc (اندازه * مورد)؛ char * p1d \u003d (char *) arr؛ char * p2d \u003d (char *) a؛ // یک نوع خالی دو بعدی را به یک بعدی برای (I \u003d 0؛ من< m; i++) { memcpy(p1d + i*sub_size, *((void**)(p2d + i*item)), sub_size); } bubbleSort3gi(arr, item, size, cmp); //Копируем одномерный массив обратно в двумерный for (i = 0; i < m; i++) { memcpy(*((void**)(p2d + i*item)), p1d + i*sub_size, sub_size); } }

اگر این ویژگی به شما اشتباه می کند، سپس از تایپ استفاده کنید. از مثال قبلی تماس بگیرید

ما یک آرایه از بالا به پایین، از عنصر صفر تا آخرین.

ایده روش: مرحله مرتب سازی شامل پاساژ از پایین تا آرایه است. در راه جفت عناصر همسایه وجود دارد. اگر عناصر برخی از جفت ها به ترتیب اشتباه باشند، ما آنها را در مکان ها تغییر می دهیم.

پس از عبور صفر با آرایه "بالا" تبدیل به عنصر "نور" است - از اینجا یک قیاس با حباب. گذرگاه زیر به عنصر دوم از بالا ساخته شده است، بنابراین دومین عنصر بزرگ به موقعیت صحیح افزایش می یابد ...

ما می توانیم برای کل بخش پایین تر از آرایه ها را کاهش دهیم تا تنها یک عنصر در آن باقی بماند. در این مرتب سازی به پایان می رسد، از آنجا که دنباله دستور صعودی است.

قالب. void bubblusort (t a، اندازه بلند) (طولانی I، j؛ t x؛ برای (i \u003d 0؛ i< size; i++) { // I - شماره عبور برای (j \u003d size-1؛ j\u003e i؛ j--) ( // چرخه عبور داخلی اگر (a\u003e a [j]) (x \u003d a؛ a \u003d a [j]؛ a [j] \u003d x؛))))

میانگین مقادیر مقایسه ها و مبادلات به ترتیب درجه دوم رشد است: تتا (n 2)، از اینجا شما می توانید نتیجه گیری کنید که الگوریتم حباب بسیار کند است و بی اثر است.
با این وجود، او دارای یک عظیم است: او ساده است و می تواند به هیچ وجه بهبود یابد. آنچه ما در حال حاضر برویم

اولا، وضعیت را در نظر بگیرید زمانی که هیچ مبادله ای بر هیچ یک از گذرها رخ نداده است. چه مفهومی داره؟

این بدان معنی است که تمام جفت ها در جهت درست قرار دارند، بنابراین آرایه در حال حاضر مرتب شده است. و برای ادامه روند، منطقی نیست (به ویژه اگر آرایه از همان ابتدا مرتب شده باشد!).

بنابراین، اولین بهبود الگوریتم این است که به یاد داشته باشید که آیا هر مبادله در این قسمت ساخته شده است. اگر نه، الگوریتم کار را پایان می دهد.

فرآیند بهبود را می توان ادامه داد اگر شما نه تنها واقعیت مبادله، بلکه شاخص آخرین تبادل K را نیز به یاد می آورید. در واقع: تمام جفت های بسته بندی عناصر با شاخص ها، کوچکتر K، در حال حاضر در سفارش دلخواه قرار دارند. Passages بیشتر می تواند بر روی شاخص k تکمیل شود، به جای حرکت به نسخه محدود محدود من نصب شده است.

به طور کیفی، بهبود دیگری در الگوریتم را می توان از مشاهدات زیر بدست آورد. اگر چه حباب نور از پایین در یک گذر افزایش می یابد، حباب های سنگین با حداقل سرعت کاهش می یابد: یک مرحله برای تکرار. بنابراین آرایه 2 3 4 5 6 1 در 1 پاس جمع آوری خواهد شد و مرتب سازی توالی 6 1 2 3 4 5 نیاز به 5 گذر دارد.

برای جلوگیری از اثر مشابه، می توانید جهت دیگری را با گذرهای دیگر تغییر دهید. الگوریتم حاصل گاهی اوقات نامیده می شود " مرتب سازی شاکر".

قالب. void shakersort (t a، اندازه طولانی) (Long J، k \u003d size-1؛ long lb \u003d 1، uB \u003d size-1؛ // مرزهای بخش ناپایدار آرایه t x؛ انجام دادن ( // عبور از پشت برای (j \u003d ub؛ j\u003e 0؛ j--) (اگر (a\u003e a [j]) (x \u003d a؛ a \u003d a [j]؛ a [j] \u003d x؛ k \u003d j؛)) lb \u003d K + 1؛ // از بالا به پایین منتقل می شود برای (j \u003d 1؛ j<=ub; j++) { if (a > a [j]) (x \u003d a؛ a \u003d a [j]؛ a [j] \u003d x؛ k \u003d j؛)) uB \u003d k-1؛ ) در حالی که (lb< ub); }

چگونه تغییرات توصیف شده بر اثربخشی روش تاثیر گذاشت؟ میانگین تعداد مقایسه ها، هرچند کاهش یافته است، اما باقی می ماند O (n 2)، در حالی که تعداد مبادلات به هیچ وجه تغییر نکرده است. متوسط \u200b\u200b(بدترین آن است) تعداد عملیات باقی می ماند درجه دوم است.

حافظه اضافی به وضوح مورد نیاز نیست. رفتار یک روش بهبود یافته (اما نه اولیه) نسبتا طبیعی است، آرایه تقریبا مرتب شده بسیار سریعتر مرتب می شود. مرتب سازی بر اساس حباب پایدار است، اما مرتب سازی شاکر این کیفیت را از دست می دهد.

در عمل، روش حباب، حتی با بهبود، کار، افسوس، خیلی آهسته است. و بنابراین - تقریبا اعمال نمی شود.

همه می دانند که از کلاس مبادله مرتب سازی سریع ترین روش به اصطلاح است مرتب سازی سریع. پایان نامه ها در مورد او نوشته شده است، مقالات زیادی در مورد هابر وجود دارد، بر اساس الگوریتم های ترکیبی پیچیده بر اساس آن است. اما امروز این کار نخواهد کرد مرتب سازی سریع، اما در مورد روش دیگری مبادله - قدیمی خوب است مرتب سازی حباب و بهبود، اصلاحات، جهش ها و ارقام آن.

اگزوز عملی از این روش ها Ahti نیست. آنچه که بسیاری از عادت ها همه اینها را در کلاس اول برگزار می کنند. بنابراین، مقاله به کسانی که فقط به تئوری الگوریتم علاقه مند هستند، مورد توجه قرار می گیرد و اولین گام ها را در این جهت می سازد.

تصویر: حباب

امروز ما در مورد ساده ترین صحبت خواهیم کرد مبادلات مرتب سازی.

اگر کسی علاقه مند باشد، من می گویم که طبقات دیگر وجود دارد - مرتب سازی انتخاب, درج مرتب سازی, مرتب سازی ادغام, توزیع مرتب سازی, مرتب سازی هیبرید و مرتب سازی موازی. به هر حال، هنوز وجود دارد مرتب سازی esoteric. این ها جعلی های مختلفی هستند، اساسا غیر واقعی، کمیک و دیگر الگوریتم های شبه، که من چند مقاله را در یک هاب "آن-طنز" بنویسید.

اما سخنرانی امروز، این مربوط نیست، ما در حال حاضر تنها برای مرتب سازی بی تکلف توسط مبادلات علاقه مند هستیم. مرتب سازی خود، همچنین بسیاری از مبادلات وجود دارد (من بیش از دوازده می دانم)، بنابراین ما به اصطلاح را در نظر می گیریم مرتب سازی حباب و برخی دیگر، با آن نزدیک به هم وابسته است.

هشدار در پیشبرد تقریبا تمام روش های فوق بسیار آهسته و تجزیه و تحلیل عمیق پیچیدگی موقت آنها نخواهد بود. بعضی از سریعتر، برخی از به یاد ماندنی ترین، اما تقریبا صحبت می کنند، می توانیم بگوییم به طور متوسط O.(n 2) من همچنین دلیل آن را نمی بینم که مقاله را با پیاده سازی در هر زبان برنامه نویسی به دست بیاوریم. علاقه مند بدون کوچکترین کار قادر به پیدا کردن نمونه هایی از کد در Rosette، ویکی پدیا و یا جایی دیگر است.

اما بازگشت به مرتب سازی مبادلات. ترتیب به عنوان یک نتیجه از شمارش متعدد سازگار از آرایه و مقایسه پارامترهای عناصر در میان خود رخ می دهد. اگر عناصر مقایسه شده توسط یکدیگر مرتب نشده باشند، ما آنها را در مکان ها تغییر می دهیم. تنها سوال دقیقا همان چیزی است که Makar آرایه به دور زدن و چه اصل انتخاب یک زن و شوهر برای مقایسه.

بیایید شروع به مرتب سازی حباب مرجع، اما از الگوریتم به نام ...

مرتب سازی احمقانه

مرتب سازی و واقعا احمقانه. ما آرایه را به سمت چپ و راست و در مقایسه با همسایگان مشاهده می کنیم. اگر ما یک زن و شوهر از عناصر متقابل متقابل را برآورده کنیم، ما آنها را در مکان ها تغییر می دهیم و به محافل برگشتیم، سپس در ابتدا به نظر میرسیم. ما عبور می کنیم، آرایه را بررسی کنید، اگر آنها دوباره "اشتباه" یک زن و شوهر از عناصر همسایه را ملاقات کنند، پس ما در مکان ها تغییر می کنیم و دوباره تمام سیزنو را شروع می کنیم. ما ادامه می دهیم تا آرایه به آرامی مرتب شود.

"بنابراین هر احمق قادر به مرتب کردن نیست" - شما می گویند و شما کاملا درست خواهد بود. به همین دلیل مرتب سازی و "احمق" نامیده می شود. در این سخنرانی، ما به طور مداوم این روش را بهبود خواهیم داد. در حال حاضر او پیچیدگی موقت دارد O.(n 3)، تولید یک اصلاح، ما را به O.(n 2)، پس شما کمی بیشتر سرعت می گیرید، پس هنوز هم، و در نهایت ما دریافت می کنیم O.(n. ورود به سیستم n.) - و آن را "سریع مرتب سازی" نخواهد بود!

ما یک پیشرفت را به صورت احمقانه معرفی می کنیم. پس از پیدا کردن دو عنصر همسایه مورد استفاده در هنگام عبور و تغییر آنها در مکان ها، من به آغاز آرایه رول نخواهم شد، و آرامش دور از دور زدن آن تا انتها.

در این مورد، قبل از ما چیزی بیش از معروف نیست ...

مرتب سازی حباب

یا مرتب سازی بر اساس مبادلات ساده. ژانر کلاسیک جاودانه. اصل عمل ساده است: دور زدن یک آرایه از ابتدا تا انتها، عبور از عناصر مجاور مجاور در طول راه. به عنوان یک نتیجه از اولین پاساژ، حداکثر عنصر "پاپ آپ" خواهد شد. حالا ما باید بخشی از آرایه ای از آرایه (از اولین عنصر را به دست بیاوریم) و تغییر مسیر همسایگان unsalted. دومین عنصر بزرگ در محل آخر قرار خواهد گرفت. ادامه در همان روح، ما از کل کاهش بخش Unsalted از آرایه عبور می کنیم، حداکثر تا انتها پیدا می کنیم.

اگر نه تنها برای قرار دادن حداکثر حداکثر برای قرار دادن حداکثر، و همچنین در ابتدا برای انتقال حداقل، پس ما ...

مرتب سازی شاکر

او است مرتب سازی بر اساس تکان دادناو است مرتب سازی کوکتل. این روند به عنوان "حباب" آغاز می شود: ما حداکثر را در حیاط خلوت فشار می دهیم. پس از آن، ما به 180 0 تبدیل می شویم و در جهت مخالف قرار می گیریم، در حالی که قبلا در ابتدا پرداخت نمی شود، حداقل و حداقل. پس از مرتب کردن عناصر اول و آخر در آرایه، ما دوباره همگی را انجام می دهیم. راه رفتن به عقب چند بار، به عنوان یک نتیجه، فرایند را پایان دهید، در وسط لیست قرار دهید.

مرتب سازی شاکر کمی سریعتر از حباب کار می کند، زیرا ماسایف در جهت راست به طور متناوب، حداکثر و حداقل را مهاجرت می کند. پیشرفت، همانطور که می گویند، واضح است.

همانطور که می بینید، اگر خلاق باشد، رد عناصر سنگین (ریه) به انتهای آرایه سریعتر است. بنابراین، صنایع دستی دیگر "نقشه راه" غیر استاندارد را برای دور زدن لیست ارائه دادند.

مرتب سازی حتی شگفت انگیز

این بار ما بر روی آرایه به عقب نشینی نمی کنیم و به نوبه خود، و به ایده از خزیدن سیستماتیک بازگشت به سمت راست، اما فقط یک گام گسترده تر. در اولین گذر، عناصر با یک کلید عجیب و غریب با همسایگان که در رای گیری ها افزایش می یابند (1-Th مقایسه از 2، سپس سوم از 4، 5، 5 از 6 و غیره). سپس، برعکس، "عناصر" خواندن "با مقایسه / تغییر با" عجیب ". سپس دوباره "چیزی" چیزی وجود دارد "، و سپس دوباره" حتی نه ". این فرآیند زمانی متوقف می شود که پس از یک قرارداد دو در امتداد ماسیف ("عجیب و غریب سیاه" و "ballotless")، نه یک مبادله واحد رخ داده است. این مرتب شد.

در هر گذرگاه "حباب" معمولی، حداکثر جریان فعلی را در انتهای آرایه فشار می دهیم. اگر انفجار شاخص های پرسشنامه و عجیب و غریب را حرکت دهید، پس از آن بلافاصله تمام عناصر بیشتر یا کمتر از آرایه به طور همزمان در یک مسافت پیموده شده به سمت راست به یک موقعیت حرکت می کنند. بنابراین سریعتر می شود.

ما دومی را می سوزانیم رنگ آمیزی* برای Sortannya Bulbashko.** - Sortanna grebinets*** این روش کاملا به سرعت سازماندهی می شود O.(n 2) بدترین پیچیدگی او. به طور متوسط \u200b\u200bما داریم O.(n. ورود به سیستم n.)، و حتی حتی، باور نکنید O.(n.) به این ترتیب، یک رقیب بسیار ارزشمند به هر "مرتب سازی سریع" و این، اطلاع، بدون استفاده از بازگشت. با این حال، من وعده داده ام که در سرعت های کروز، ما به سرعت کروز نمی رویم، سکوت می کنم و آن را به طور مستقیم به الگوریتم تبدیل می کنم.

لاک پشت به سرزنش

پیش از تاریخ کوچک در سال 1980، Vlodzimezh Doboshevich توضیح داد که چرا حباب ها و مشتقات مرتب سازی به آرامی کار می کنند. این همه به خاطر لاک پشت ها است. "لاک پشت ها" - اقلام کوچک که در انتهای لیست هستند. همانطور که ممکن است متوجه نشر حباب متمرکز بر "خرگوش" (نه به اشتباه با "خرگوش" Babushkina) - بزرگ در معنای عناصر در ابتدای لیست. آنها بسیار محکم به پایان می رسند. اما خزندگان آرام آرام آرام آرام آرام خواهند شد. سفارشی "tortila" می تواند استفاده کند محاسبات.

تصویر: لاک پشت گناه

محاسبه مرتب سازی

در "حباب"، "شاکر" و "حتی بدون نیاز"، با یک توده در آرایه، عناصر مجاور مقایسه می شوند. ایده اصلی "محاسبات" این است که ابتدا فاصله ای به اندازه کافی بین عناصر محرمانه داشته باشیم و به عنوان آرایه از آرایه ناشی می شود، حداقل آن است. بنابراین، همانطور که بود، ما یک آرایه را ترکیب می کنیم، به تدریج بر روی رشته های به طور فزاینده ای صاف می شود.

شکاف اولیه بین عناصر محرمانه بهتر است که هیچ ABBA را نپردازید، بلکه با توجه به اندازه خاص نامیده می شود کاهش فاکتور، ارزش مطلوب آن تقریبا 1.247 است. اول، فاصله بین عناصر برابر با اندازه آرایه جامد است عامل کاهش (نتیجه، به طور طبیعی، به نزدیکترین کل گرد می شود). سپس، عبور از آرایه با این مرحله، ما گام را تقسیم می کنیم عامل کاهش و ما دوباره از طریق لیست می رویم. این تا زمانی که تفاوت های شاخص به واحد برسد ادامه می یابد. در این مورد، آرایه توسط یک حباب معمولی ارتباطی ندارد.

روش تجربه و نظری، ارزش مطلوب است. کاهش فاکتور:

هنگامی که این روش اختراع شد، تعداد کمی از مردم در محل اتصال 70s و 80 به آن توجه کردند. دهه بعد، زمانی که برنامه ریزی، بسیاری از دانشمندان و مهندسان IBM را متوقف کرده است، و در حال حاضر به طور کامل به دست آمده از طبیعت عظیم به دست آورد، این روش در سال 1991 بازرسی، تحقیق و محبوب در سال 1991 استفان لسی و ریچارد بوکس باز شد.

این در واقع، و همه چیز که من می خواستم به شما در مورد مرتب سازی حباب و دیگران مانند آن بگویید.

- یادداشت

* نقاشی شده ( uKR) - بهبود
** SortVania Bulbashko ( uKR) - مرتب سازی بر اساس حباب
*** Sorthanny Grebinzts ( uKR) - مرتب سازی محاسبه

سلام همه!

امروز ما مرتب سازی بر اساس روش "حباب" را بررسی خواهیم کرد. این الگوریتم اغلب در مدارس و دانشگاه ها استفاده می شود، بنابراین ما از زبان پاسکال استفاده خواهیم کرد. و بنابراین مرتب سازی چیست؟ مرتب سازی مرتب سازی عناصر کوچکتر به بیشتر (مرتب سازی در صعودی) یا از یک عنصر بزرگتر به کوچکتر (مرتب سازی نزولی). مرتب سازی معمولا آرایه ها.

الگوریتم های مرتب سازی مختلف وجود دارد. برخی، به خوبی مرتب کردن تعداد زیادی از عناصر، دیگر، کارآمدتر با تعداد بسیار کمی از اقلام. روش حباب ما مشخص است:

طرفداران:

• آسان برای پیاده سازی الگوریتم
• اسم زیبا

معایب:

• یکی از کمترین روش های مرتب سازی (زمان اجرای چهار درجه بستگی به طول آرایه N 2 دارد)
• تقریبا در زندگی واقعی استفاده نمی شود (به طور عمده برای اهداف آموزشی استفاده می شود)

اجازه دهید ما یک آرایه خاص داشته باشیم: 3 1 4 2

الگوریتم: ما یک عنصر از آرایه را مصرف می کنیم، اگر عنصر ما، بیش از مورد بعدی، با موارد زیر، مقایسه کنیم، سپس آنها را در مکان ها تغییر می دهیم. پس از عبور از کل آرایه، می توانیم مطمئن باشیم که حداکثر عنصر "تحت فشار" قرار می گیرد - و بیشترین دومی را تحمل می کند. بنابراین، یک عنصر در حال حاضر دقیقا در جای خود است. زیرا ما باید همه آنها را در جای خود قرار دهیم، بنابراین ما باید این عملیات را تکرار کنیم، همانطور که بسیاری از عناصر آرایه منهای 1. آخرین عنصر به طور خودکار به طور خودکار ایستاده ایم، اگر بقیه در مکان های خود ایستاده باشند.

بیایید به آرایه ما بازگردیم: 3 1 4 2
ما عنصر اول "3" را با مقایسه "1" زیر می گیریم. زیرا "3"\u003e "1"، سپس مکان ها را عوض می کنیم:
1 3 4 2
در حال حاضر مقایسه "3" و "4"، Troika بیش از چهارم نیست، به این معنی نیست. بعد، مقایسه "4" و "2". چهار بیش از دو - به این معنی است که ما مکان ها را عوض می کنیم: 1 3 2 4. چرخه به پایان رسید. بنابراین بزرگترین عنصر در حال حاضر باید در جای خود ایستاده! ما می بینیم که ما اتفاق افتاده ایم. هر کجا که "4" (بزرگترین عنصر ما) نبود - او هنوز هم، پس از عبور از چرخه کل آرایه، آخرین خواهد بود. آنالوگ - به عنوان یک حباب هوا شناور در آب - هر دو عنصر ما در یک آرایه ظاهر می شود. بنابراین، الگوریتم "مرتب سازی حباب" نامیده می شود. برای قرار دادن آیتم بعدی، ابتدا باید چرخه را شروع کنید، اما آخرین عنصر دیگر نمی تواند در نظر گرفته شود، زیرا در جای خود قرار دارد.

مقایسه "1" و "3" - ما چیزی را تغییر نمی دهیم.
مقایسه "3" و "2" - سه بیش از دو، سپس ما مکان ها را تغییر می دهیم. به نظر می رسد: 1 2 3 4. چرخه دوم تکمیل شد ما قبلا دو دوره را ساختیم - به این معنی است که ما می توانیم بگوییم که ما داریم، دو عنصر اخیر در حال حاضر مرتب شده اند. این عنصر سوم را مرتب می کند، و چهارم، به طور خودکار در جای مناسب افزایش می یابد. بار دیگر، ما عنصر اول و دوم را مقایسه می کنیم - ما می بینیم که ما همه چیز را در مکان هایمان داریم، به این معنی است که یک آرایه را می توان در نظر گرفت، با افزایش عناصر مرتب شده است.

در حال حاضر این الگوریتم را در زبان پاسکال برنامه ریزی می کند. const n \u003d 4؛ (ما ثابت را به ارمغان می آوریم، طول آرایه) var i، j، k، k: integer؛ (دو متغیر برای چرخه سرمایه گذاری، یکی به منظور تغییر عناصر در مکان ها) M: آرایه ای از عدد صحیح؛ (ما آرایه را می آوریم) شروع می کنیم (ما یک آرایه از صفحه کلید را درخواست خواهیم کرد :) Writeln ("یک آرایه را وارد کنید")؛ برای من: \u003d 1 به N شروع به شروع Writeln (I، "عنصر:")؛ readln (m [i])؛ پایان؛ (چرخه خارجی مسئول این واقعیت است که ما باید چرخه درونی را چندین بار به عنوان عناصر آرایه منهای منفی تکرار کنیم.) برای I: \u003d 1 به N-1 شروع می شود (چرخه داخلی در حال حاضر موارد را حرکت می دهد و یکدیگر را مقایسه می کند.) برای J: \u003d 1 به NI شروع می شود (اگر یک عنصر، بیش از بعد، پس از آن تغییر مکان ها.) اگر m [j]\u003e مردان شروع k: \u003d m [j]؛ m [j]: \u003d m؛ m: \u003d k؛ پایان؛ پایان؛ پایان؛ (خروجی نتیجه :) برای من: \u003d 1 به N نوشتن (m [i]، "")؛ پایان.
در اینجا نتیجه است:

اما آموزش تصویری

مرتب سازی بر اساس حباب - ساده ترین الگوریتم مرتب سازی به صورت صرفا برای اهداف آموزشی اعمال می شود. هیچ کاربردی عملی برای این الگوریتم وجود ندارد، زیرا این امر موثر نیست، مخصوصا اگر لازم باشد آرایه بزرگ را مرتب کنید. مزایای مرتب سازی با یک حباب شامل سادگی اجرای الگوریتم است.

حباب الگوریتم مرتب سازی به تکرار عبارات توسط عناصر آرایه مرتب شده می رسد. عبور از عناصر آرایه چرخه داخلی را انجام می دهد. برای هر گذر، دو عنصر مجاور مقایسه شده اند، و اگر سفارش موارد نادرست مکان های تغییر مکان را تغییر دهد. چرخه بیرونی کار خواهد کرد تا آرایه مرتب شود. بنابراین، چرخه خارجی تعداد پاسخ های چرخه داخلی را کنترل می کند، زمانی که، با عبور بعدی، هیچ جایگزینی بر عناصر آرایه وجود نخواهد داشت، آرایه مرتب می شود. برای درک الگوریتم به خوبی، روش حباب را مرتب کنید، به عنوان مثال، از 7 عدد (جدول 1 را ببینید).
آرایه منبع: 3 3 7 1 2 5 0

جدول 1 - مرتب سازی بر اساس حباب

شماره تکرار	عناصر آرایه							مجددا مرتب شده
تبادل آرایه	3	3	7	1	2	5	0
0	3	3						اشتباه
1		3	7					اشتباه
2			1	7				7\u003e 1، درست است
3				2	7			7\u003e 2، درست است
4					5	7		7\u003e 5، درست است
5						0	7	7\u003e 0، درست است
تکنولوژی آرایه	3	3	1	2	5	0	7
0	3	3						اشتباه
1		1	3					3\u003e 1، درست است
2			2	3				3\u003e 2، درست است
3				0	3			3\u003e 0، درست است
4					3	5		اشتباه
5						5	7	اشتباه
تکنولوژی آرایه	3	1	2	0	3	5	7
0	1	3						3\u003e 1، درست است
1		2	3					3\u003e 2، درست است
2			0	3				3\u003e 0، درست است
3				3	3			اشتباه
4					3	5		اشتباه
5						5	7	اشتباه
تکنولوژی آرایه	1	2	0	3	3	5	7
	1	2						اشتباه
		0	2					2\u003e 0، درست است
			2	3				اشتباه
				3	3			اشتباه
					3	5		اشتباه
						5	7	اشتباه
تکنولوژی آرایه	1	0	2	3	3	5	7
	0	1						1\u003e 0، درست است
		1	2					اشتباه
			2	3				اشتباه
				3	3			اشتباه
					3	5		اشتباه
						5	7	اشتباه
آرایه	0	1	2	3	3	5	7
پایان مرتب سازی

به منظور مرتب سازی آرایه ای از پنج راه اندازی چرخه داخلی، برای. در حال اجرا، چرخه برای 6 بار باعث شد، از آنجا که اقلام در یک آرایه 7، پس از آن تکرار (تکرار) از چرخه باید کمتر باشد. هر تکرار دو عنصر مجاور آرایه را مقایسه می کند. اگر عنصر فعلی آرایه بیش از بعد باشد، آنها را در مکان ها تغییر دهید. بنابراین، تا زمانی که آرایه مرتب شود، چرخه داخلی راه اندازی خواهد شد و عملیات مقایسه انجام خواهد شد. توجه داشته باشید که برای هر اجرای کامل A برای حداقل یک عنصر از آرایه جای خود را پیدا می کند. در بدترین حالت، N-2 از راه اندازی چرخه درونی، که N تعداد عناصر آرایه است، می گیرد. این نشان می دهد که مرتب سازی حباب برای آرایه های بزرگ بسیار موثر نیست.

ما یک برنامه را توسعه خواهیم داد که در آن شما ابتدا باید اندازه یک آرایه یک بعدی را وارد کنید، پس از آن آرایه با اعداد تصادفی پر شده و توسط یک روش حباب مرتب شده است.

// bu_sort.cpp: نقطه ورودی را برای برنامه کنسول تعیین می کند. #include "stdafx.h" #include #عبارتند از. #عبارتند از. استفاده از Namespace STD؛ void bubblesort (int *، int)؛ // مرتب سازی عملکرد نمونه اولیه توسط حباب INT اصلی (int argc، char * argv) (srand (زمان (زمان (null)؛ setlocale (lc_all، "rus")؛ cout<< "Введите размер массива: "; int size_array; // длинна массива cin >\u003e size_array؛ int * sorted_array \u003d int جدید؛ // آرایه پویا یک بعدی برای (int counter \u003d 0؛ شمارنده< size_array; counter++) { sorted_array = rand() % 100; // заполняем массив случайными числами cout << setw(2) << sorted_array << " "; // вывод массива на экран } cout << "\n\n"; bubbleSort(sorted_array, size_array); // вызов функции сортировки пузырьком for (int counter = 0; counter < size_array; counter++) { cout << setw(2) << sorted_array << " "; // печать отсортированного массива } cout << "\n"; system("pause"); return 0; } void bubbleSort(int* arrayPtr, int length_array) // сортировка пузырьком { int temp = 0; // временная переменная для хранения элемента массива bool exit = false; // болевая переменная для выхода из цикла, если массив отсортирован while (!exit) // пока массив не отсортирован { exit = true; for (int int_counter = 0; int_counter < (length_array - 1); int_counter++) // внутренний цикл //сортировка пузырьком по возрастанию - знак > // مرتب سازی بر اساس حباب نزولی - نشانه< if (arrayPtr > ArrayPtr) // مقایسه دو عنصر مجاور (// permutation از عناصر temp \u003d arrayptr آرایه را انجام دهید؛ arrayptr \u003d arrayptr؛ arrayptr \u003d temp؛ خروج \u003d false؛ // در تکرار بعدی، عناصر مجددا مرتب شده اند))

نتیجه برنامه در شکل 1 نشان داده شده است.