مرتب سازی سریع در جاوا (Quick Sort)

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

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

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

هر پیاده‌سازی این الگوریتم به‌صورت کلی از دو بخش تشکیل شده‌است. یک بخش تقسیم‌بندی آرایه (partition) و قسمت مرتب کردن. روش مرتب‌سازی سریع (Quick Sort) یکی از الگوریتم‌های مشهور مرتب‌سازی داده‌ها است. این الگوریتم طی مراحل بازگشتی زیر یک روش تقسیم و غلبه برای مرتب کردن داده‌ها ارائه می‌نماید:

1. انتخاب عنصر محوری: یکی از عناصر آرایه به عنوان عنصر محوری (pivot) – به عنوان مثال عنصر اول – انتخاب می‌شود.
2. تقسیم آرایه: چینش عناصر آرایه به قسمی تغییر داده می‌شود که تمامی عناصر کوچکتر یا مساوی محور در سمت چپ آن، و تمامی عناصر بزرگتر در سمت راست آن قرار بگیرند. این دو قسمت زیر آرایه‌های چپ و راست نامیده می‌شوند.
3. مرتب‌سازی بازگشتی: زیرآرایه‌های چپ و راست به روش مرتب‌سازی سریع مرتب می‌شوند(ویکیپدیا)

پیاده سازی مرتب سازی سریع در جاوا

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

  private static void quicksort(int[] a, int s, int e) {
          if(s>=e)
              return;
          int q = partition(a,s,e);
          quicksort(a, s, q-1);
          quicksort(a, q+1, e);

     }

     private static int partition(int[] a, int s, int e) {
          int x = a[e];
          int i = s-1;
          for(int j = s;j<e;++j){
              if(a[j]<=x){
                   ++i;
                   int temp = a[i];
                   a[i]= a[j];
                   a[j]=temp;
              }
          }
          ++i;
          int temp = a[i];
          a[i]= a[e];
          a[e]=temp;
          return i;
     }

کد مرتب سازی سریع در جاوا دارای دو متد میباشد

1. Quicksort
2. Partion

در متد quicksort ما آرایه را partition میکنیم و بر اساس pivot بقیه آرایه را مرتب میکنیم. در متد partition ابتدا عنصر آخر را pivot میگیریم سپس خانه های کوچکتر از آن را از اول آرایه شروع به چیدن میکنیم(خانه های قبل از pivot مرتب نیستند و فقط کوچکتر از pivot هستند). سپس که کل آرایه را چرخیدیم عنصر pivot را در مکان خود قرار میدهیم(pivot باید بعد از خانه هایی باشد که میدانیم از آن کوچکتر هستند. متغیر i در کد بالا همین کار میکند).

تست مرتبسازی سریع درجاوا

برای اجرای برنامه بالا کد main زیر را بنویسید.

   public static void main(String[] args) {

     int a[] = {5,4,3,2,1};
     quicksort(a, 0, a.length-1);

     System.out.println(Arrays.toString(a));



     }

خروجی برنامه

[1, 2, 3, 4, 5]