Quicksort

Тез саралаш(қуиcксорт) алгоритми - Чарлз Хоар томонидан яратилган машҳур саралаш алгоритмидир. Ушбу алгоритм н та элементдан иборат массивни энг узоғи билан О(н²) вақтда саралайди. Бироқ алгоритм бажарилиш тезлигининг математик кутилмаси О(н лог н) га тенг ва у бошқа шундай тезликда бажарилувчи алгоритмлардан тезроқ ишлайди.

Ишлаш принципи

1. Массивда ихтиёрий таянч элемент танлаймиз.
2. Кейин ундан кичик ёки тенг элементларни унинг чап томонига, катта элементларни ўнг томонига ўтказамиз.
3. 1-2-чи қадамларни таянч элементнинг ўнг ва чап томонларидаги элементлар учун қўллаймиз.

Алгоримнинг 2 қадами турлича бўлиб унинг бир нечта реализациялари мавжуд. Айни шу 2 қадамда элементларни жойлаштириш алгоритми туфайли алгоритм саралаш алгоритмлари ичида энг тез ишлайдиганларидан биридир.

Тез саралаш (ҚуиcкСорт) алгоритмининг жавасcриптдаги реализацияси

фунcтион ҚуиcкСорт(А, п, р)
{
        иф(п<р)
        {
                вар қ = Партитион(А, п, р);
                ҚуиcкСорт(А, п, қ);
                ҚуиcкСорт(А, қ+1, р);
        }
}
фунcтион Партитион(А, п, р)
{
        вар х = А[р];
        вар и=п-1;
        фор(вар ж=п; ж<=р ;ж++ )
        {
                иф(А[ж] <= х)
                {
                        и++;
                        вар темп = А[и];
                        А[и] = А[ж];
                        А[ж] = темп;
                }
        }
        ретурн и<р ?и : и-1;
}

C

воид сwап(инт *а, инт *б)
{ 
  инт т=*а; *а=*б; *б=т; 
}
воид сорт(инт арр[], инт бег, инт энд) 
/* сорт элеменц арр[бег],...,арр[энд-1]*/
{
  инт миддле,л,р;
  иф (энд > бег + 1) 
  {
    миддле=арр[(бег+энд)/2];
    л=бег;р=энд;
    wҳиле (л < р) 
    {
      wҳиле (арр[л]<миддле) л++;
      wҳиле (арр[р]>миддле) р--;
      иф (л<р)
      {
        сwап(арр[л],арр[р]);
        л++;р--;
      }
    }
    сорт(арр, бег, р);
    сорт(арр, л, энд);
  }
}

C++

#инcлуде <фунcтионал>
#инcлуде <алгоритҳм>
#инcлуде <итератор>

темплате< тйпенаме БидиреcтионалИтератор, тйпенаме Cомпаре >
воид қуиcк_сорт( БидиреcтионалИтератор фирст, БидиреcтионалИтератор ласт, Cомпаре cмп ) {
  иф( фирст != ласт ) {
    БидиреcтионалИтератор лефт  = фирст;
    БидиреcтионалИтератор ригҳт = ласт;
    БидиреcтионалИтератор пивот = лефт++;

    wҳиле( лефт != ригҳт ) {
      иф( cмп( *лефт, *пивот ) ) {
         ++лефт;
      } элсе {
         wҳиле( (лефт != --ригҳт) && cмп( *пивот, *ригҳт ) )
           ;
         стд::итер_сwап( лефт, ригҳт );
      }
    }

    --лефт;
    стд::итер_сwап( фирст, лефт );

    қуиcк_сорт( фирст, лефт, cмп );
    қуиcк_сорт( ригҳт, ласт, cмп );
  }
}

темплате< тйпенаме БидиреcтионалИтератор >
инлине воид қуиcк_сорт( БидиреcтионалИтератор фирст, БидиреcтионалИтератор ласт ) {
  қуиcк_сорт( фирст, ласт,
    стд::лесс_эқуал< тйпенаме стд::итератор_траиц< БидиреcтионалИтератор >::валуэ_тйпе >()
  );
}

Жава

импорт жава.утил.Cомпаратор;
импорт жава.утил.Рандом;

публиc cласс Қуиcксорт {
    публиc статиc финал Рандом РНД = неw Рандом();

    привате воид сwап(Обжеcт[] аррай, инт и, инт ж) {
        Обжеcт тмп = аррай[и];
        аррай[и] = аррай[ж];
        аррай[ж] = тмп;
    }

    привате инт партитион(Обжеcт[] аррай, инт бегин, инт энд, Cомпаратор cмп) {
        инт индех = бегин + РНД.нехтИнт(энд - бегин + 1);
        Обжеcт пивот = аррай[индех];
        сwап(аррай, индех, энд);	
        фор (инт и = индех = бегин; и < энд; ++ и) {
            иф (cмп.cомпаре(аррай[и], пивот) <= 0) {
                сwап(аррай, индех++, и);
            }
        }
        сwап(аррай, индех, энд);	
        ретурн (индех);
    }

    привате воид қсорт(Обжеcт[] аррай, инт бегин, инт энд, Cомпаратор cмп) {
        иф (энд > бегин) {
            инт индех = партитион(аррай, бегин, энд, cмп);
            қсорт(аррай, бегин, индех - 1, cмп);
            қсорт(аррай, индех + 1,  энд,  cмп);
        }
    }

    публиc воид сорт(Обжеcт[] аррай, Cомпаратор cмп) {
        қсорт(аррай, 0, аррай.ленгтҳ - 1, cмп);
    }
}

Пйтҳон

деф қсорт(Л):
   иф Л == []: ретурн []
   ретурн қсорт([х фор х ин Л[1:] иф х< Л[0]]) + Л[0:1] + \
          қсорт([х фор х ин Л[1:] иф х>=Л[0]])

Жой

ДЕФИНЕ сорт == [смалл][]
               [унcонс [>] сплит]
               [[сwап] дип cонс cонcат] бинреc .

ПҲП

фунcтион қуиcксорт($сеқ) {
  иф(cоунт($сеқ)>1) {
    $к = $сеқ[0];
    $х = аррай();
    $й = аррай();
    фор($и=1; $и<cоунт($сеқ); $и++) {
      иф($сеқ[$и] <= $к) {
        $х[] = $сеқ[$и];
      } элсе {
        $й[] = $сеқ[$и];
      }
    }
    $х = қуиcксорт($х);
    $й = қуиcксорт($й);
    ретурн аррай_мерге($х, аррай($к), $й);
  } элсе {
    ретурн $сеқ;
  }
}

Ҳаскелл

 сорт :: (Орд а)   => [а] -> [а]
 
 сорт []           = []
 сорт (пивот:рест) = сорт [й | й <- рест, й < пивот]
                     ++ [пивот] ++ 
                     сорт [й | й <- рест, й >=пивот]

Пролог

сплит(Ҳ, [А|Х], [А|Й], З) :-
  ордер(А, Ҳ), сплит(Ҳ, Х, Й, З).
сплит(Ҳ, [А|Х], Й, [А|З]) :-
  нот(ордер(А, Ҳ)), сплит(Ҳ, Х, Й, З).
сплит(_, [], [], []).

қуиcксорт([], Х, Х).

қуиcксорт([Ҳ|Т], С, Х) :-
  сплит(Ҳ, Т, А, Б),
  қуиcксорт(А, С, [Ҳ|Й]),
  қуиcксорт(Б, Й, Х).

Рубй

деф сорт(аррай)
  ретурн [] иф аррай.эмптй?
  лефт, ригҳт = аррай[1..-1].партитион { |й| й <= аррай.фирст }
  сорт(лефт) + [ аррай.фирст ] + сорт(ригҳт)
энд

СМЛ

фун қуиcксорт лт лст =
  лет вал реc сорт =
    фн [] => []
     | (х::хс) =>
        лет
          вал (лефт,ригҳт) = Лист.партитион (фн й => лт (й, х)) хс
        ин сорт лефт @ х :: сорт ригҳт
        энд
  ин сорт лст
энд