ਇੱਕ ਪਰੋਗਰਾਮਿੰਗ ਵਿਧੀ ਦੇ ਤੌਰ ਤੇ Quicksort

1960 ਵਿੱਚ, ਕੇ ਏ ਕੋਰੇ ਜਾਣਕਾਰੀ ਦੇ ਤੇਜ਼ੀ ਨਾਲ ਲੜੀਬੱਧ ਕਰਨ ਲਈ ਇੱਕ ਵਿਧੀ ਤਿਆਰ, ਸਭ ਮਸ਼ਹੂਰ ਹੋ ਗਿਆ. ਅੱਜ ਇਸ ਨੂੰ ਵਿਆਪਕ, ਪ੍ਰੋਗਰਾਮਿੰਗ ਵਿੱਚ ਵਰਤਿਆ ਗਿਆ ਹੈ ਦੇ ਰੂਪ ਵਿੱਚ ਇਸ ਨੂੰ ਸਕਾਰਾਤਮਕ ਹੋਣ ਦੇ ਇੱਕ ਬਹੁਤ ਕੁਝ ਹੈ: ਇਸ ਨੂੰ ਆਮ ਕੇਸ ਲਈ ਵਰਤਿਆ ਜਾ ਸਕਦਾ ਹੈ, ਇਸ ਨੂੰ ਵਾਧੂ ਯਾਦ ਵਿਚ ਇਕ ਛੋਟਾ ਵਾਧਾ, ਦੀ ਸੂਚੀ ਦੇ ਵੱਖ-ਵੱਖ ਕਿਸਮ ਦੇ ਅਨੁਕੂਲ ਹੈ ਅਤੇ ਲਾਗੂ ਕਰਨ ਲਈ ਆਸਾਨ ਦੀ ਲੋੜ ਹੈ. ਪਰ, ਨੁਕਸਾਨ ਹਨ, ਜੋ ਕਿ Quicksort ਹੈ: ਵਰਤ ਦੇ ਕੰਮ ਗਲਤੀ ਦਾ ਇੱਕ ਬਹੁਤ ਸਾਰਾ ਦੀ ਇਜਾਜ਼ਤ ਹੈ, ਅਤੇ ਇਸ ਨੂੰ ਥੋੜਾ ਅਸਥਿਰ ਹੈ.

ਪਰ, ਇਸ ਨੂੰ ਸਭ ਦਾ ਅਧਿਐਨ ਵਰਜਨ ਹੈ. ਪਹਿਲੇ ਦਾ ਭੁਗਤਾਨ Hoare ਬਾਅਦ, ਬਹੁਤ ਸਾਰੇ ਇਸ ਦੇ ਸੰਘਣੀ ਦਾ ਅਧਿਐਨ ਕਰਦੇ ਹਨ. ਵੱਡੇ ਅਧਾਰ ਨੂੰ ਟਾਈਮ ਨੌਕਰੀ ਹੈ, ਜੋ ਕਿ ਅਨੁਭਵੀ ਸਬੂਤ underpinned ਹੈ 'ਤੇ ਖਰਚ ਨੂੰ ਲੱਭਣ ਦੇ ਲਿਖਤੀ ਸਵਾਲ' ਤੇ ਸਥਾਪਤ ਕੀਤਾ ਗਿਆ ਸੀ. ਉੱਥੇ ਬੁਨਿਆਦੀ ਐਲਗੋਰਿਥਮ ਅਤੇ ਵਧੀ ਗਤੀ ਨੂੰ ਸੁਧਾਰ ਕਰਨ ਲਈ ਅਸਲੀ ਪ੍ਰਸਤਾਵ ਸੀ.

Quicksort ਬਹੁਤ ਹੀ ਆਮ ਹੈ, ਇਸ ਨੂੰ ਹਰ ਜਗ੍ਹਾ ਲੱਭਿਆ ਜਾ ਸਕਦਾ ਹੈ. ਇਸ ਦੇ ਆਧਾਰ 'ਤੇ ਢੰਗ ਦੀ TList.Sort, ਸਾਰੇ ਵਰਜਨ (ਨੂੰ ਛੱਡ ਕੇ 1) ਡੈਲਫੀ, ਵਾਰ ਦੀ ਲਾਇਬਰੇਰੀ ਫੰਕਸ਼ਨ ਇਸ ਨੂੰ C ਵਿੱਚ ਪੂਰਾ ਕਰਨ ਲਈ, qsort ++ ਲਿਆ ਹੈ ਵਿੱਚ ਮੌਜੂਦ ਲਾਗੂ ਕੀਤਾ ਗਿਆ ਹੈ.

ਕਾਰਵਾਈ ਦੇ ਬੁਨਿਆਦੀ ਅਸੂਲ ਇੱਕ "ਫੁੱਟ ਪਾਵੇ" ਦੇ ਤੌਰ ਤੇ ਤਿਆਰ ਕੀਤਾ ਜਾ ਸਕਦਾ ਹੈ. ਇਹ ਦੋ ਗਰੁੱਪ ਵਿੱਚ ਸੂਚੀ ਵਿੱਚ ਤੋੜ ਹੁੰਦੀ ਹੈ ਅਤੇ ਆਪਣੇ ਆਪ ਨੂੰ ਦੇ ਕੇ ਹਰ ਹਿੱਸੇ ਲਈ ਕ੍ਰਮਬੱਧ ਕਰ ਰਹੇ ਹਨ. ਇਹ ਹੈ ਕਿ ਜ਼ਿਆਦਾ ਧਿਆਨ ਵੱਖ ਕਾਰਜ ਨੂੰ, ਜਿਸ ਦੌਰਾਨ ਹੇਠ ਲਿਖੇ ਵਾਪਰਦਾ ਹੈ ਨੂੰ ਭੁਗਤਾਨ ਕੀਤਾ ਜਾਣਾ ਚਾਹੀਦਾ ਹੈ: ਇੱਕ ਅਧਾਰ ਤੱਤ ਕਰਕੇ ਪਤਾ ਹੈ ਅਤੇ ਮੁਕਾਬਲਤਨ ਉਸ ਦੀ ਸਾਰੀ ਸੂਚੀ ਨੂੰ ਬਦਲਦੇ ਕੀਤਾ ਹੈ. ਉਮੀਦਵਾਰ ਦੇ ਇੱਕ ਸਮੂਹ ਦੇ ਖੱਬੇ ਬਿੱਲਟ, ਮੁੱਲ, ਜਿਸ ਦੇ ਹੋਰ ਸਾਰੇ ਤਬਾਦਲੇ ਦੇ ਨਿਯਮ ਵੱਧ ਘੱਟ ਹੈ. ਇਹ ਬਾਹਰ ਕਾਮੁਕ ਹੈ, ਜੋ ਕਿ ਕ੍ਰਮਬੱਧ ਸੂਚੀ ਵਿੱਚ ਮੁੱਖ ਤੱਤ ਇਸ ਦੇ ਹੱਕ ਜਗ੍ਹਾ ਵਿੱਚ ਹੈ. ਅਗਲੇ ਪੜਾਅ - ਤੱਤ ਅਧਾਰ ਨੂੰ ਰਿਸ਼ਤੇਦਾਰ ਦੇ ਦੋਨੋ ਪਾਸੇ ਦੇ ਲਈ ਇਕ ਚੁਣੌਤੀ ਲਗਾਤਾਰ ਲੜੀਬੱਧ ਫੰਕਸ਼ਨ. ਇਹ ਖਤਮ ਹੁੰਦਾ ਹੈ ਕਾਰਵਾਈ ਨੂੰ ਕੰਮ ਕਰਦਾ ਹੈ, ਸਿਰਫ ਜੇ ਸੂਚੀ ਵਿੱਚ ਸਿਰਫ ਇੱਕ ਹੀ ਤੱਤ ਸ਼ਾਮਿਲ ਹੈ, ਜੋ ਕਿ ਕ੍ਰਮਬੱਧ ਕੀਤਾ ਗਿਆ ਹੈ. ਇਸ ਲਈ, ਇੱਕ ਤੇਜ਼ ਲੜੀਬੱਧ ਦੇ ਤੌਰ ਤੇ ਇੱਕ ਪ੍ਰੋਗਰਾਮਿੰਗ ਫੰਕਸ਼ਨ ਪੰਗਾ ਕਰਨ ਲਈ, ਇਸ ਨੂੰ ਜ਼ਰੂਰੀ ਹੇਠਲੇ ਪੱਧਰ ਦੇ ਐਲਗੋਰਿਥਮ ਦਾ ਕੰਮ ਨੂੰ ਪਤਾ ਕਰਨ ਲਈ ਹੈ: ੳ) ਦਾ ਅਧਾਰ ਮਬਰ ਦੀ ਪਸੰਦ ਅਨੁਸਾਰ; ਅ) ਸਭ ਪ੍ਰਭਾਵਸ਼ਾਲੀ permutation ਦੀ ਇੱਕ ਸੂਚੀ ਛੋਟੇ ਅਤੇ ਵੱਡੇ ਮੁੱਲ ਦੇ ਨਾਲ ਦੋ ਸੈੱਟ ਪੈਦਾ ਕਰਨ ਲਈ.

ਪਹਿਲੇ ਅਸੂਲ ਨਾਲ ਜਾਣੂ. ਜਦ ਅਧਾਰ ਨੂੰ ਅੰਗ ਦੀ ਚੋਣ, ਆਦਰਸ਼ਕ ਔਸਤ ਦੀ ਸੂਚੀ ਚੁਣਿਆ ਜਾਣਾ ਚਾਹੀਦਾ ਹੈ. ਫਿਰ ਬ੍ਰੇਕ 'ਤੇ ਦੋ ਬਰਾਬਰ ਅੱਧੇ ਵਿੱਚ ਵੰਡਿਆ ਗਿਆ ਹੈ. ਬਸ ਦਾ ਹਿਸਾਬ ਔਸਤ ਮੁੱਲ ਸੂਚੀ ਵਿੱਚ ਬਹੁਤ ਹੀ ਮੁਸ਼ਕਲ ਹੁੰਦਾ ਹੈ, ਇਸ ਲਈ ਵੀ ਤੇਜ਼ ਲੜੀਬੱਧ ਇਸ ਕਲਕੂਲਸ ਪਾਸੇ ਨੂੰ ਬਾਏਪਾਸ. ਪਰ ਵੱਧ ਜ ਘੱਟੋ-ਘੱਟ ਮੁੱਲ ਦੇ ਨਾਲ ਬੁਨਿਆਦੀ ਤੱਤ ਦੀ ਪਸੰਦ - ਵਧੀਆ ਚੋਣ ਨੂੰ ਵੀ ਨਾ. ਕੇਸ ਵਿੱਚ ਇੱਕ ਦੇ ਅਜਿਹੇ ਇਰਾਦੇ ਨੂੰ ਖਾਲੀ ਸੂਚੀ ਨੂੰ ਗਾਰੰਟੀ ਕੀਤਾ ਜਾਵੇਗਾ, ਅਤੇ ਦੂਜਾ ਪੂਰੀ ਬਣਾਉਦਾ ਹੈ. ਇਸ ਲਈ ਸਿੱਟਾ ਹੈ, ਜੋ ਕਿ ਅਧਾਰ ਨੂੰ ਅੰਗ ਦੇ ਤੌਰ ਤੇ, ਜੋ ਕਿ ਇੱਕ ਔਸਤ ਦੇ ਨੇੜੇ ਹੈ ਨੂੰ ਚੁਣਿਆ ਜਾਣਾ ਚਾਹੀਦਾ ਹੈ, ਪਰ ਵੱਧ ਹੈ ਅਤੇ ਘੱਟੋ-ਘੱਟ 'ਤੇ.

ਇੱਕ ਵਾਰ ਇੱਕ ਵਿਕਲਪ ਦਾ ਪੱਕਾ ਇਰਾਦਾ ਕੀਤਾ ਹੈ, ਤੁਹਾਨੂੰ ਸੜਨ ਐਲਗੋਰਿਥਮ ਲਈ ਜਾਰੀ ਕਰ ਸਕਦਾ ਹੈ. ਇਹ ਤੇਜ਼ ਲੜੀਬੱਧ ਇਸ ਲਈ-ਕਹਿੰਦੇ ਅੰਦਰਲੇ ਇਹਨਆ. ਹਰ ਚੀਜ਼ ਦੇ ਦੋ ਤੇਜ਼ ਪਹੁੰਚ ਇੰਡੈਕਸ 'ਤੇ ਬਣਾਇਆ ਗਿਆ ਹੈ: ਪਹਿਲੀ, ਤੱਤ ਦਾ ਹੱਕ, ਦੂਜਾ ਖੱਬੇ ਉਲਟ' ਤੇ, 'ਤੇ ਜਾਣ ਦਾ ਹੱਕ ਛੱਡ ਦਿੱਤਾ ਤੱਕ. ਸ਼ੁਰੂ ਕਾਰਵਾਈ ਚੱਲਣ ਦਾ ਹੱਕ: ਸੂਚੀ-ਪੱਤਰ ਸੂਚੀ 'ਤੇ ਹੈ ਅਤੇ ਮੁੱਖ ਕਰਨ ਲਈ ਸਾਰੇ ਮੁੱਲ ਦੀ ਤੁਲਨਾ ਕਰੋ. ਚੱਕਰ ਪੂਰਾ ਹੋ ਗਿਆ ਹੈ, ਜਦ ਕਿ ਤੱਤ ਬੇਸਲਾਈਨ ਦਾ ਵੱਧ ਘੱਟ ਜ ਬਰਾਬਰ ਹੁੰਦਾ ਹੈ. ਇਹ ਇਕ ਤੁਲਨਾ ਹੁੰਦਾ ਹੈ ਅਤੇ ਇੰਡੈਕਸ ਦਾ ਮੁੱਲ ਵੀ ਘਟਦੀ ਹੈ, ਹੈ. ਖੱਬੇ ਪਾਸੇ 'ਤੇ ਕੰਮ ਵੱਧ ਜ ਬਰਾਬਰ ਮੁੱਲ ਵੱਡਾ ਪੂਰਾ ਹੋ ਗਿਆ ਹੈ. ਇੱਥੇ, ਤੁਲਨਾ ਮੁੱਲ ਵਾਧੇ.

ਵਿਭਾਗੀਕਰਨ ਐਲਗੋਰਿਥਮ ਹੈ, ਜੋ ਕਿ quicksort ਬਣਿਆ ਦੇ ਇਸ ਪੜਾਅ 'ਤੇ, ਦੋ ਹਾਲਾਤ ਪੈਦਾ ਹੋ ਸਕਦਾ ਹੈ. ਪਹਿਲੀ ਹੈ, ਜੋ ਕਿ ਖੱਬੇ ਪਾਸੇ ਸੂਚੀ-ਪੱਤਰ ਦਾ ਹੱਕ ਵੱਧ ਘੱਟ ਹੈ. ਇਹ ਇੱਕ ਗਲਤੀ ਦੱਸਦਾ ਹੈ, ਫਿਰ ਤੱਤ, ਜਿਸ 'ਤੇ ਇਸ ਨੂੰ ਸੂਚੀ ਵਿੱਚ ਕਿਹਾ ਗਿਆ ਸੀ ਨੂੰ ਗਲਤ ਕ੍ਰਮ ਵਿੱਚ ਹਨ. ਆਉਟਪੁੱਟ - ਆਪਣੇ ਸਥਾਨ ਨੂੰ ਬਦਲਣ. ਦੂਜਾ ਸਥਿਤੀ ਨੂੰ ਜਦ ਕਾਲਮ ਦੇ ਦੋਨੋ ਦੇ ਬਰਾਬਰ ਜ ਪਾਰ ਹੈ. ਇਹ ਸੂਚੀ ਦੇ ਇੱਕ ਸਫਲ ਵੱਖ ਪਤਾ ਲੱਗਦਾ ਹੈ, ਜੋ ਕਿ ਹੈ, ਦਾ ਕੰਮ ਹੁਣ ਪੂਰਾ ਹੋ ਗਿਆ ਹੈ.