b'\n_START_ARTICLE_\n\xc4\x80tr\xc4\x81s k\xc4\x81rto\xc5\xa1anas algoritms\n_START_PARAGRAPH_\n\xc4\x80tr\xc4\x81s k\xc4\x81rto\xc5\xa1anas algoritms ir k\xc4\x81rto\xc5\xa1anas algoritms, kuru izstr\xc4\x81d\xc4\x81ja Sers \xc4\x8c\xc4\x81rlzs Antonijs Ri\xc4\x8dards Hoars (C.A.R. Hoare) Britu datorzin\xc4\x81tnieks 1960. gad\xc4\x81 kad bija 26 gadus vecs, un tas ir viens no pla\xc5\xa1\xc4\x81k izmantotajiem k\xc4\x81rto\xc5\xa1anas algoritmiem. \xc5\xa0\xc4\xab algoritma vid\xc4\x93j\xc4\x81 sare\xc5\xbe\xc4\xa3\xc4\xabt\xc4\xabba ir . Slikt\xc4\x81kaj\xc4\x81 gad\xc4\xabjum\xc4\x81 algoritma sare\xc5\xbe\xc4\xa3\xc4\xabt\xc4\xabba ir  tom\xc4\x93r, ja algoritmu lieto pareizi, tad \xc5\xa1\xc4\x81ds gad\xc4\xabjums ir nov\xc4\x93rojams reti. Parasti \xc4\x81tr\xc4\x81s k\xc4\x81rto\xc5\xa1anas algoritms ir \xc4\x81tr\xc4\x81ks k\xc4\x81 citi  sare\xc5\xbe\xc4\xa3\xc4\xabt\xc4\xabbas k\xc4\x81rto\xc5\xa1anas algoritmi, galvenok\xc4\x81rt t\xc4\x81d\xc4\x93\xc4\xbc, ka algoritma iek\xc5\xa1\xc4\x93jais cikls ir viegli uzlabojams un piem\xc4\x93rojams nepiecie\xc5\xa1amajam gad\xc4\xabjumam. \xc4\x80tr\xc4\x81s k\xc4\x81rto\xc5\xa1anas algoritma lab\xc4\x81s \xc4\xabpa\xc5\xa1\xc4\xabbas ir k\xc4\x81rto\xc5\xa1ana bez papildu atmi\xc5\x86as (tiek izmantots neliels steks), mazais sal\xc4\xabdzin\xc4\x81\xc5\xa1anu skaits, k\xc4\x81 ar\xc4\xab algoritma \xc4\xabsais iek\xc5\xa1\xc4\x93jais cikls.\n_START_SECTION_\nV\xc4\x93sture\n_START_PARAGRAPH_\n\xc4\x80tr\xc4\x81s k\xc4\x81rto\xc5\xa1anas algoritmu izstr\xc4\x81d\xc4\x81ja Sers \xc4\x8c\xc4\x81rlzs Antonijs Ri\xc4\x8dards Hoars (C.A.R. Hoare) Britu datorzin\xc4\x81tnieks 1960. gad\xc4\x81 kad bija 26 gadus vecs, un tas ir viens no pla\xc5\xa1\xc4\x81k izmantotajiem k\xc4\x81rto\xc5\xa1anas algoritmiem. Tas tika izstr\xc4\x81d\xc4\x81ts, laik\xc4\x81 kad t\xc4\x81 autors atrad\xc4\x81s Padomju Savien\xc4\xabb\xc4\x81 Maskavas Universit\xc4\x81t\xc4\x93 k\xc4\x81 apmai\xc5\x86as students, algoritma m\xc4\x93r\xc4\xb7is bija sak\xc4\x81rtot tulkot nepiecie\xc5\xa1amos v\xc4\x81rdus t\xc4\x81, lai tie b\xc5\xabtu vienk\xc4\x81r\xc5\xa1\xc4\x81k saist\xc4\xabti sav\xc4\x81 starp\xc4\x81.\n_START_SECTION_\nSare\xc5\xbe\xc4\xa3\xc4\xabt\xc4\x81 versija\n_START_PARAGRAPH_\nVienk\xc4\x81r\xc5\xa1\xc4\x81s versijas m\xc4\xabnuss ir t\xc4\x81ds, ka to izmantojot nepiecie\xc5\xa1ama O(n) papildus atmi\xc5\x86a, kas ir tikpat daudz cik tiek izmantots k\xc4\x81rto\xc5\xa1anai ar sapludin\xc4\x81\xc5\xa1anu (merge sort). Papildus atmi\xc5\x86as pras\xc4\xabba var b\xc5\xabtiski ietekm\xc4\x93t algoritma darb\xc4\xabbas \xc4\x81trumu un ke\xc5\xa1atmi\xc5\x86as darb\xc4\xabbu praktisk\xc4\x81 algoritma pielietojum\xc4\x81. Lai nov\xc4\x93rstu vienk\xc4\x81r\xc5\xa1\xc4\x81s versijas tr\xc5\xabkumus ir izstr\xc4\x81d\xc4\x81ts \xc4\x81tr\xc4\x81s k\xc4\x81rto\xc5\xa1anas algoritms, kur\xc5\xa1 sp\xc4\x93j sak\xc4\x81rtot datus vid\xc4\x93ji izmantojot O(log n) papildus atmi\xc5\x86u. \xc4\x80tr\xc4\x81s k\xc4\x81rto\xc5\xa1anas algoritma dal\xc4\xab\xc5\xa1anas funkcijas pseidokods izskat\xc4\x81s sekojo\xc5\xa1i:_NEWLINE__NEWLINE_  function partition(array, left, right, pivotIndex)_NEWLINE_        pivotValue := array[pivotIndex]_NEWLINE_        swap array[pivotIndex] and array[right] // P\xc4\x81rvietot dal\xc4\xabt\xc4\x81ju uz beig\xc4\x81m_NEWLINE_        storeIndex := left_NEWLINE_        for i  from  left to right - 1 // left \xe2\x89\xa4 i < right _NEWLINE_            if array[i] \xe2\x89\xa4 pivotValue_NEWLINE_                swap array[i] and array[storeIndex]_NEWLINE_                storeIndex := storeIndex + 1_NEWLINE_        swap array[storeIndex] and array[right] // P\xc4\x81rvietot dal\xc4\xabt\xc4\x81ju uz t\xc4\x81 gala poz\xc4\xabciju_NEWLINE_        return storeIndex_NEWLINE_\xc5\xa0is dal\xc4\xab\xc5\xa1anas algoritma pseidokods nav t\xc4\x81ds k\xc4\x81du to izstr\xc4\x81d\xc4\x81ja \xc4\x8c\xc4\x81rlzs Antonijs Ri\xc4\x8dards Hoars, past\xc4\x81v v\xc4\x93l citas dal\xc4\xab\xc5\xa1anas funkcijas priek\xc5\xa1 \xc4\x81tr\xc4\x81s k\xc4\x81rto\xc5\xa1anas algoritma, tom\xc4\x93r \xc5\xa1o saprast ir nedaudz viegl\xc4\x81k k\xc4\x81 citas._NEWLINE_Kad dal\xc4\xab\xc5\xa1anas funkcija ir izveidota uzrakst\xc4\xabt \xc4\x81tr\xc4\x81s k\xc4\x81rto\xc5\xa1anas algoritmu vairs nav tik sare\xc5\xbe\xc4\xa3\xc4\xabti un tas ir sekojo\xc5\xa1s:_NEWLINE__NEWLINE_  procedure quicksort(array, left, right)_NEWLINE_       if right > left_NEWLINE_           select a pivot index //(e.g. pivotIndex := left+(right-left)/2)_NEWLINE_           pivotNewIndex := partition(array, left, right, pivotIndex)_NEWLINE_           quicksort(array, left, pivotNewIndex - 1)_NEWLINE_           quicksort(array, pivotNewIndex + 1, right)_NEWLINE_Tom\xc4\x93r t\xc4\x81, k\xc4\x81 dal\xc4\xab\xc5\xa1anas funkcija p\xc4\x81rk\xc4\x81rto elementus katr\xc4\x81 da\xc4\xbc\xc4\x81, tad \xc5\xa1\xc4\xab \xc4\x81tr\xc4\x81s k\xc4\x81rto\xc5\xa1anas algortima versija nav stabila._NEWLINE_\xc5\xa0\xc4\xab ir v\xc4\x93l viena \xc4\x81tr\xc4\x81s k\xc4\x81rto\xc5\xa1anas algoritma versija, kas darbojas ar nelielu papildus atmi\xc5\x86u:_NEWLINE__NEWLINE_ function quicksort(array, left, right)_NEWLINE_     var pivot, leftIdx = left, rightIdx = right_NEWLINE_     if right - left > 0_NEWLINE_         pivot = (left + right) / 2_NEWLINE_         while leftIdx <= pivot and rightIdx >= pivot_NEWLINE_             while array[leftIdx] < array[pivot] and leftIdx <= pivot_NEWLINE_                 leftIdx = leftIdx + 1_NEWLINE_             while array[rightIdx] > array[pivot] and rightIdx >= pivot_NEWLINE_                 rightIdx = rightIdx - 1;_NEWLINE_             swap array[leftIdx] with array[rightIdx]_NEWLINE_             leftIdx = leftIdx + 1_NEWLINE_             rightIdx = rightIdx - 1_NEWLINE_             if leftIdx - 1 == pivot_NEWLINE_                 pivot = rightIdx = rightIdx + 1_NEWLINE_             else if rightIdx + 1 == pivot_NEWLINE_                 pivot = leftIdx = leftIdx - 1_NEWLINE_         quicksort(array, left, pivot - 1)_NEWLINE_         quicksort(array, pivot + 1, right)\n_START_SECTION_\nDal\xc4\xabt\xc4\x81ja izv\xc4\x93le\n_START_PARAGRAPH_\nS\xc4\x81kotn\xc4\x93j\xc4\x81 algoritma versij\xc4\x81 par dal\xc4\xabt\xc4\x81ju tika izv\xc4\x93l\xc4\x93ts kreisais pirmais elements no k\xc4\x81rtojamo elementu saraksta, tom\xc4\x93r t\xc4\x81da dal\xc4\xabt\xc4\x81ja izv\xc4\x93le rada slikt\xc4\x81k\xc4\x81 varianta sare\xc5\xbe\xc4\xa3\xc4\xabt\xc4\xabbu  gandr\xc4\xabz sak\xc4\x81rtotiem failiem, kas ir diezgan bie\xc5\xbea par\xc4\x81d\xc4\xabba praktisk\xc4\x81 pielietojum\xc4\x81. \xc5\xa0\xc4\xab probl\xc4\x93ma tika nov\xc4\x93rsta par izveidojot dal\xc4\xab\xc5\xa1anas funkciju, kas par dal\xc4\xabt\xc4\x81ju katru reizi izv\xc4\x93las nejau\xc5\xa1u elementu, vid\xc4\x93jo elementu, vai p\xc4\x93d\xc4\x93jo elementu no faila.'