ਕੰਪਿਊਟਰ ਵਿਗਿਆਨ ਐਲਗੋਰਿਦਮ ਅਤੇ ਡੇਟਾ ਢਾਂਚੇ ਦੀਆਂ ਗੁੰਝਲਾਂ ਨੂੰ ਸਮਝਣ ਬਾਰੇ ਹੈ।
ਤੁਹਾਡੇ ਕੋਲ ਉਹਨਾਂ ਆਈਟਮਾਂ ਦੀ ਸੂਚੀ ਹੈ ਜਿਨ੍ਹਾਂ ਨੂੰ ਛਾਂਟਣ ਦੀ ਲੋੜ ਹੈ, ਪਰ ਤੁਹਾਡੇ ਕੋਲ ਵਧੇਰੇ ਗੁੰਝਲਦਾਰ ਛਾਂਟੀ ਕਰਨ ਵਾਲੇ ਐਲਗੋਰਿਦਮ ਦੀ ਵਰਤੋਂ ਕਰਨ ਲਈ ਸਮਾਂ ਜਾਂ ਸਰੋਤ ਨਹੀਂ ਹਨ।
ਸੰਮਿਲਨ ਛਾਂਟੀ ਸਭ ਤੋਂ ਸਰਲ ਲੜੀਬੱਧ ਐਲਗੋਰਿਦਮ ਵਿੱਚੋਂ ਇੱਕ ਹੈ, ਪਰ ਇਹ ਵੱਡੀਆਂ ਸੂਚੀਆਂ ਲਈ ਹੌਲੀ ਹੋ ਸਕਦੀ ਹੈ।
ਆਸਾਨ ਲਾਗੂ ਕਰਨ ਅਤੇ ਸਮਝ ਨੇ ਇਸ ਵਿਧੀ ਨੂੰ ਪ੍ਰੋਗਰਾਮਰਾਂ ਵਿੱਚ ਇੱਕ ਪਸੰਦੀਦਾ ਬਣਾ ਦਿੱਤਾ ਹੈ। ਇਹ ਛੋਟੀਆਂ ਸੂਚੀਆਂ ਲਈ ਸੰਪੂਰਣ ਹੈ ਜਾਂ ਜਦੋਂ ਤੁਹਾਨੂੰ ਤੁਰੰਤ ਹੱਲ ਦੀ ਲੋੜ ਹੁੰਦੀ ਹੈ।
ਇਸ ਬਲਾੱਗ ਪੋਸਟ ਵਿੱਚ, ਅਸੀਂ ਸੰਮਿਲਨ ਛਾਂਟੀ ਦੀ ਸਮੇਂ ਦੀ ਗੁੰਝਲਤਾ ਨੂੰ ਵੇਖਾਂਗੇ। ਇਹ ਐਲਗੋਰਿਦਮ ਐਰੇ ਨੂੰ ਕ੍ਰਮਬੱਧ ਕਰਨ ਲਈ ਵਰਤਿਆ ਜਾਂਦਾ ਹੈ, ਅਤੇ ਇਸਦਾ ਰਨਟਾਈਮ O(n2). ਇਸਦਾ ਮਤਲਬ ਹੈ ਕਿ ਸਮੇਂ ਦੀ ਗੁੰਝਲਤਾ ਐਰੇ ਦੇ ਆਕਾਰ ਦੇ ਨਾਲ ਵਧਦੀ ਹੈ.
ਹਾਲਾਂਕਿ, ਇਹ ਐਲਗੋਰਿਦਮ ਹੋਰ ਛਾਂਟਣ ਵਾਲੇ ਐਲਗੋਰਿਦਮ, ਜਿਵੇਂ ਕਿ ਕੁਇੱਕਸੋਰਟ, ਨਾਲੋਂ ਅਕਸਰ ਤੇਜ਼ ਹੋ ਸਕਦਾ ਹੈ।
ਆਉ ਇਸ ਗੱਲ 'ਤੇ ਡੂੰਘਾਈ ਨਾਲ ਵਿਚਾਰ ਕਰੀਏ ਕਿ ਸੰਮਿਲਨ ਛਾਂਟੀ ਕਿਵੇਂ ਕੰਮ ਕਰਦੀ ਹੈ!
ਸੰਮਿਲਨ ਲੜੀਬੱਧ ਐਲਗੋਰਿਦਮ ਕੀ ਹੈ?
ਇੱਕ ਸਮੇਂ ਵਿੱਚ ਇੱਕ ਤੱਤ, ਸੰਮਿਲਨ ਕ੍ਰਮ ਇੱਕ ਛਾਂਟਣਯੋਗ ਐਰੇ ਬਣਾਉਂਦਾ ਹੈ, ਜਿਸਨੂੰ ਅਕਸਰ ਇੱਕ ਸੂਚੀ ਕਿਹਾ ਜਾਂਦਾ ਹੈ।
ਉਦਾਹਰਨ ਲਈ, ਛਾਂਟੀ ਨੂੰ ਗੁੰਝਲਦਾਰ ਕੰਪਿਊਟਰ ਪ੍ਰੋਗਰਾਮਾਂ ਜਿਵੇਂ ਕਿ ਕੰਪਾਈਲਰ ਵਿੱਚ ਲਾਗੂ ਕੀਤਾ ਜਾਂਦਾ ਹੈ, ਜਿੱਥੇ ਪ੍ਰੋਗਰਾਮ ਦੀ ਵਿਆਖਿਆ ਲਈ ਟੋਕਨਾਂ ਦਾ ਕ੍ਰਮ ਮਹੱਤਵਪੂਰਨ ਹੁੰਦਾ ਹੈ।
ਸੰਮਿਲਨ ਛਾਂਟੀ ਕਿਵੇਂ ਕੰਮ ਕਰਦੀ ਹੈ?
ਜਦੋਂ ਅਸੀਂ ਇੱਕ ਐਰੇ ਨੂੰ ਕ੍ਰਮਬੱਧ ਕਰਨ ਲਈ ਸੰਮਿਲਨ ਲੜੀ ਦੀ ਵਰਤੋਂ ਕਰਦੇ ਹਾਂ, ਤਾਂ ਐਲਗੋਰਿਦਮ ਸੂਚੀ ਵਿੱਚ ਸਭ ਤੋਂ ਛੋਟੀ ਆਈਟਮ ਨੂੰ ਲੱਭ ਕੇ ਅਤੇ ਇਸਨੂੰ ਸਹੀ ਸਥਿਤੀ ਵਿੱਚ ਸ਼ਾਮਲ ਕਰਕੇ ਸ਼ੁਰੂ ਕਰਦਾ ਹੈ।
ਇਹ ਫਿਰ ਅਗਲੀ ਸਭ ਤੋਂ ਛੋਟੀ ਆਈਟਮ ਨੂੰ ਲੱਭਦਾ ਹੈ ਅਤੇ ਇਸਨੂੰ ਸਹੀ ਸਥਿਤੀ ਵਿੱਚ ਦਾਖਲ ਕਰਦਾ ਹੈ, ਅਤੇ ਇਸ ਤਰ੍ਹਾਂ ਹੀ.
ਐਲਗੋਰਿਦਮ ਸੂਚੀ ਨੂੰ ਲੂਪ ਕਰਕੇ, ਹਰੇਕ ਆਈਟਮ ਦੀ ਤੁਲਨਾ ਇਸ ਤੋਂ ਪਹਿਲਾਂ ਆਉਣ ਵਾਲੀ ਆਈਟਮ ਨਾਲ ਕਰਦਾ ਹੈ।
ਜੇਕਰ ਆਈਟਮਾਂ ਗਲਤ ਕ੍ਰਮ ਵਿੱਚ ਹਨ, ਤਾਂ ਐਲਗੋਰਿਦਮ ਉਹਨਾਂ ਨੂੰ ਬਦਲ ਦਿੰਦਾ ਹੈ। ਇਹ ਫਿਰ ਇਹ ਦੇਖਣ ਲਈ ਜਾਂਚ ਕਰਦਾ ਹੈ ਕਿ ਕੀ ਸੂਚੀ ਨੂੰ ਕ੍ਰਮਬੱਧ ਕੀਤਾ ਗਿਆ ਹੈ, ਅਤੇ ਜੇਕਰ ਇਹ ਹੈ, ਤਾਂ ਐਲਗੋਰਿਦਮ ਖਤਮ ਹੁੰਦਾ ਹੈ.
ਅਭਿਆਸ ਵਿੱਚ, ਸੰਮਿਲਨ ਲੜੀ ਨੂੰ ਅਕਸਰ ਕੋਡ ਦੀਆਂ ਕੁਝ ਲਾਈਨਾਂ ਦੀ ਵਰਤੋਂ ਕਰਕੇ ਲਾਗੂ ਕੀਤਾ ਜਾਂਦਾ ਹੈ, ਇਸ ਨੂੰ ਛੋਟੀਆਂ ਐਰੇ ਨੂੰ ਛਾਂਟਣ ਲਈ ਇੱਕ ਪ੍ਰਸਿੱਧ ਵਿਕਲਪ ਬਣਾਉਂਦਾ ਹੈ। ਹਾਲਾਂਕਿ, ਇਸ ਐਲਗੋਰਿਦਮ ਦੀ ਵਰਤੋਂ ਕਰਦੇ ਸਮੇਂ ਸਮੇਂ ਦੀ ਗੁੰਝਲਤਾ ਨੂੰ ਵਿਚਾਰਿਆ ਜਾਣਾ ਚਾਹੀਦਾ ਹੈ।
ਉਦਾਹਰਨ:
ਇੱਥੇ ਇੱਕ ਉਦਾਹਰਨ ਹੈ ਕਿ ਸੰਮਿਲਨ ਛਾਂਟੀ ਕਿਵੇਂ ਕੰਮ ਕਰਦੀ ਹੈ। ਅਸੀਂ ਹੇਠਾਂ ਦਿੱਤੀ ਐਰੇ ਦੀ ਵਰਤੋਂ ਕਰਾਂਗੇ:
1, 2, 3, 4, 5, 6
ਐਲਗੋਰਿਦਮ ਸੂਚੀ ਵਿੱਚ ਸਭ ਤੋਂ ਛੋਟੀ ਆਈਟਮ ਨੂੰ ਲੱਭ ਕੇ ਸ਼ੁਰੂ ਹੁੰਦਾ ਹੈ, ਜੋ ਕਿ 1 ਹੈ। ਇਹ ਫਿਰ ਇਸਨੂੰ ਸਹੀ ਸਥਿਤੀ, ਪਹਿਲੀ ਸਥਿਤੀ ਵਿੱਚ ਸੰਮਿਲਿਤ ਕਰਦਾ ਹੈ। ਇਹ ਫਿਰ ਅਗਲੀ ਸਭ ਤੋਂ ਛੋਟੀ ਚੀਜ਼ ਲੱਭਦਾ ਹੈ, ਜੋ ਕਿ 2 ਹੈ। ਇਹ ਇਸਨੂੰ ਸਹੀ ਸਥਿਤੀ ਵਿੱਚ ਸ਼ਾਮਲ ਕਰਦਾ ਹੈ, ਜੋ ਕਿ ਦੂਜੀ ਸਥਿਤੀ ਹੈ।
ਇਹ ਫਿਰ ਅਗਲੀ ਸਭ ਤੋਂ ਛੋਟੀ ਚੀਜ਼ ਲੱਭਦਾ ਹੈ, ਜੋ ਕਿ 3 ਹੈ. ਇਹ ਇਸਨੂੰ ਸਹੀ ਸਥਿਤੀ ਵਿੱਚ ਸ਼ਾਮਲ ਕਰਦਾ ਹੈ, ਜੋ ਕਿ ਤੀਜੀ ਸਥਿਤੀ ਹੈ।
ਇਹ ਫਿਰ ਅਗਲੀ ਸਭ ਤੋਂ ਛੋਟੀ ਚੀਜ਼ ਲੱਭਦਾ ਹੈ, ਜੋ ਕਿ 4 ਹੈ। ਇਹ ਇਸਨੂੰ ਸਹੀ ਸਥਿਤੀ ਵਿੱਚ ਸ਼ਾਮਲ ਕਰਦਾ ਹੈ, ਜੋ ਕਿ ਚੌਥੀ ਸਥਿਤੀ ਹੈ, ਅਤੇ ਇਸ ਤਰ੍ਹਾਂ ਹੀ। ਸੂਚੀ ਨੂੰ ਹੁਣ ਕ੍ਰਮਬੱਧ ਕੀਤਾ ਗਿਆ ਹੈ!
ਅਸੀਂ ਉਦਾਹਰਨ ਤੋਂ ਦੇਖ ਸਕਦੇ ਹਾਂ ਕਿ ਐਲਗੋਰਿਦਮ ਸੂਚੀ ਨੂੰ ਛਾਂਟਣ ਲਈ ਛੇ ਤੁਲਨਾਵਾਂ ਅਤੇ ਸਵੈਪ ਕਰਦਾ ਹੈ। ਇਹ ਇਸ ਲਈ ਹੈ ਕਿਉਂਕਿ ਇਹ ਐੱਨ2 n ਆਈਟਮਾਂ ਦੀ ਸੂਚੀ ਨੂੰ ਛਾਂਟਣ ਲਈ ਤੁਲਨਾਵਾਂ ਅਤੇ ਸਵੈਪ। ਇਸ ਕੇਸ ਵਿੱਚ, n = 6.
ਸੰਮਿਲਨ ਕ੍ਰਮਬੱਧ ਸਮੇਂ ਦੀ ਗੁੰਝਲਤਾ ਨੂੰ ਕਿਵੇਂ ਸੁਧਾਰਿਆ ਜਾਵੇ?
ਜਦੋਂ ਕਿ ਸੰਮਿਲਨ ਕ੍ਰਮ ਵਿੱਚ O(n2), ਇਸ ਨੂੰ ਇੱਕ ਬਿਹਤਰ ਲੜੀਬੱਧ ਐਲਗੋਰਿਦਮ ਦੀ ਵਰਤੋਂ ਕਰਕੇ ਸੁਧਾਰਿਆ ਜਾ ਸਕਦਾ ਹੈ, ਜਿਵੇਂ ਕਿ ਕਵਿੱਕਸੋਰਟ।
Quicksort ਕੋਲ ਇੱਕ O(n log n) ਰਨਟਾਈਮ ਹੈ, ਜੋ ਕਿ O(n) ਨਾਲੋਂ ਬਹੁਤ ਤੇਜ਼ ਹੈ2).
ਹਾਲਾਂਕਿ, ਕੁਝ ਮਾਮਲਿਆਂ ਵਿੱਚ, ਸੰਮਿਲਨ ਛਾਂਟੀ ਕੁਇੱਕਸੋਰਟ ਨਾਲੋਂ ਤੇਜ਼ ਹੋ ਸਕਦੀ ਹੈ।
ਉਦਾਹਰਨ ਲਈ, ਜੇਕਰ ਸੂਚੀ ਪਹਿਲਾਂ ਤੋਂ ਹੀ ਕ੍ਰਮ ਵਿੱਚ ਹੈ, ਤਾਂ ਸੰਮਿਲਨ ਛਾਂਟੀ ਕਰਨ ਵਿੱਚ ਕੁਇੱਕਸੋਰਟ ਨਾਲੋਂ ਘੱਟ ਸਮਾਂ ਲੱਗੇਗਾ।
ਅਭਿਆਸ ਵਿੱਚ, ਸੰਮਿਲਨ ਲੜੀ ਨੂੰ ਅਕਸਰ ਕੋਡ ਦੀਆਂ ਕੁਝ ਲਾਈਨਾਂ ਦੀ ਵਰਤੋਂ ਕਰਕੇ ਲਾਗੂ ਕੀਤਾ ਜਾਂਦਾ ਹੈ, ਇਸ ਨੂੰ ਛੋਟੀਆਂ ਐਰੇ ਨੂੰ ਛਾਂਟਣ ਲਈ ਇੱਕ ਪ੍ਰਸਿੱਧ ਵਿਕਲਪ ਬਣਾਉਂਦਾ ਹੈ।
ਹਾਲਾਂਕਿ, ਇਸ ਐਲਗੋਰਿਦਮ ਦੀ ਵਰਤੋਂ ਕਰਦੇ ਸਮੇਂ ਸਮੇਂ ਦੀ ਗੁੰਝਲਤਾ ਨੂੰ ਵਿਚਾਰਿਆ ਜਾਣਾ ਚਾਹੀਦਾ ਹੈ।
ਸਮੇਂ ਦੀਆਂ ਜਟਿਲਤਾਵਾਂ
ਸਭ ਤੋਂ ਮਾੜੇ ਕੇਸ ਦੀ ਜਟਿਲਤਾ O(n2):
ਸਮੇਂ ਦੀ ਗੁੰਝਲਤਾ ਐਰੇ ਦੇ ਆਕਾਰ ਦੇ ਨਾਲ ਵਧਦੀ ਹੈ। ਇਹ ਐੱਨ2 n ਆਈਟਮਾਂ ਦੀ ਸੂਚੀ ਨੂੰ ਛਾਂਟਣ ਲਈ ਤੁਲਨਾਵਾਂ ਅਤੇ ਸਵੈਪ।
ਉਦਾਹਰਨ ਲਈ, ਜੇਕਰ ਸਾਡੇ ਕੋਲ ਆਕਾਰ 1000 ਦੀ ਇੱਕ ਐਰੇ ਹੈ, ਤਾਂ ਐਲਗੋਰਿਦਮ ਐਰੇ ਨੂੰ ਛਾਂਟਣ ਲਈ 1,000,000 ਤੁਲਨਾਵਾਂ ਅਤੇ ਸਵੈਪ ਲਵੇਗਾ।
ਵਧੀਆ ਕੇਸ ਜਟਿਲਤਾ O(n):
ਸਮੇਂ ਦੀ ਗੁੰਝਲਤਾ ਇੰਪੁੱਟ ਐਰੇ ਦੇ ਆਕਾਰ ਦੇ ਬਰਾਬਰ ਹੈ। ਆਈ
n ਆਈਟਮਾਂ ਦੀ ਸੂਚੀ ਨੂੰ ਛਾਂਟਣ ਲਈ t ਤੁਲਨਾ ਅਤੇ ਸਵੈਪ ਕਰਦਾ ਹੈ। ਉਦਾਹਰਨ ਲਈ, ਆਕਾਰ 5 ਦੀ ਇੱਕ ਐਰੇ 'ਤੇ ਵਿਚਾਰ ਕਰੋ। ਐਲਗੋਰਿਦਮ ਐਰੇ ਨੂੰ ਛਾਂਟਣ ਲਈ ਪੰਜ ਤੁਲਨਾਵਾਂ ਅਤੇ ਸਵੈਪ ਲਵੇਗਾ।
ਔਸਤ ਕੇਸ ਜਟਿਲਤਾ O(n2):
ਸਮੇਂ ਦੀ ਗੁੰਝਲਤਾ ਇਸ ਕੇਸ ਵਿੱਚ ਸਭ ਤੋਂ ਭੈੜੇ ਅਤੇ ਸਭ ਤੋਂ ਵਧੀਆ ਕੇਸ ਦੀਆਂ ਜਟਿਲਤਾਵਾਂ ਵਿਚਕਾਰ ਹੈ।
ਇਹ ਐੱਨ2 n ਆਈਟਮਾਂ ਦੀ ਸੂਚੀ ਨੂੰ ਛਾਂਟਣ ਲਈ ਤੁਲਨਾਵਾਂ ਅਤੇ ਸਵੈਪ।
ਇਸ ਤਰ੍ਹਾਂ, ਸੰਮਿਲਨ ਛਾਂਟੀ ਇੱਕ ਸਥਿਰ ਲੜੀਬੱਧ ਐਲਗੋਰਿਦਮ ਹੈ।
ਸੰਮਿਲਨ ਛਾਂਟੀ ਸਥਿਰ ਕਿਉਂ ਹੈ?
ਸੰਮਿਲਨ ਕ੍ਰਮ ਸਥਿਰ ਹੈ ਕਿਉਂਕਿ ਇਹ ਇੰਪੁੱਟ ਐਰੇ ਵਿੱਚ ਬਰਾਬਰ ਤੱਤਾਂ ਦੇ ਕ੍ਰਮ ਨੂੰ ਸੁਰੱਖਿਅਤ ਰੱਖਦਾ ਹੈ।
ਇਹ ਬਹੁਤ ਸਾਰੀਆਂ ਐਪਲੀਕੇਸ਼ਨਾਂ ਲਈ ਮਹੱਤਵਪੂਰਨ ਹੈ, ਜਿਵੇਂ ਕਿ ਡਾਟਾ ਪ੍ਰਾਪਤੀ ਜਾਂ ਵਿੱਤੀ ਵਿਸ਼ਲੇਸ਼ਣ। ਉਦਾਹਰਨ ਲਈ, ਜੇਕਰ ਸਾਡੇ ਕੋਲ ਸੰਖਿਆਵਾਂ ਦੀਆਂ ਦੋ ਸੂਚੀਆਂ ਹਨ ਅਤੇ ਅਸੀਂ ਉਹਨਾਂ ਦੀ ਤੁਲਨਾ ਕਰਨਾ ਚਾਹੁੰਦੇ ਹਾਂ, ਤਾਂ ਸਾਨੂੰ ਇਹ ਯਕੀਨੀ ਬਣਾਉਣ ਦੀ ਲੋੜ ਹੈ ਕਿ ਤੱਤਾਂ ਦਾ ਕ੍ਰਮ ਸੁਰੱਖਿਅਤ ਹੈ।
ਜੇਕਰ ਸੂਚੀਆਂ ਨੂੰ ਕ੍ਰਮਬੱਧ ਨਹੀਂ ਕੀਤਾ ਗਿਆ ਹੈ, ਤਾਂ ਅਸੀਂ ਉਹਨਾਂ ਦੀ ਸਹੀ ਤੁਲਨਾ ਨਹੀਂ ਕਰਾਂਗੇ।
ਕੋਈ ਜਵਾਬ ਛੱਡਣਾ