You are not logged in. Please login at www.codechef.com to post your questions!

×

Counting sort is called stable and non-comparison sort.

Why counting sort is called stable and non-comparison sort?

asked 17 Jan '17, 00:05

rashedcs's gravatar image

2★rashedcs
49751452
accept rate: 4%


@rashedcs It's a non-comparison sorting technique as it works by counting the number of elements having distinct key values and then doing some arithmetic to calculate the position of each element in the output sequence and hence it does not compare elements to sort unlike other commonly used sorting technique like merge sort, quick sort, etc.,

Consider an example when you find an item with key x, knowing that it may have other information that distinguishes it from other items with the same key, you don't just increment a counter for bucket x (which would discard all those extra information). Instead, you have a linked list (or similarly ordered data structure with constant time amortized append) for each bucket, and you append that item to the end of the list for bucket x as you scan the input left to right. So, it just dumps them back into one sorted list. For a better explanation, you can refer to this answer(link).

link

answered 17 Jan '17, 00:52

srd091's gravatar image

5★srd091
1.6k111
accept rate: 42%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×834

question asked: 17 Jan '17, 00:05

question was seen: 826 times

last updated: 17 Jan '17, 00:52