Be yourself; Everyone else is already taken.
— Oscar Wilde.
This is the first post on my new blog. I’m just getting this new blog going, so stay tuned for more. Subscribe below to get notified when I post new updates.
Selection of Sorting Method in Computer Science
Sorting is one of the major problems in Computer Science and Engineering. One needs to sort data in an ascending or a descending order based on problem statement. Efficient sorting is required to optimize the performance of other algorithms such as searching and merging. There are two types of sorting methods viz. Comparison Based Sorting and Non-comparison Based Sorting. In Comparison Based Sorting methods , elements are compared with each other to get the sorted order. In Non-comparison Based Sorting methods, elements are not compared with each other to get sorted order. Bubble Sort, Insertion Sort, Selection Sort, Merge Sort, Quick Sort, Heap Sort, and Shell Sort are examples of Comparison Based Sorting methods whereas Radix Sort, Count Sort, and Bucket Sort are examples of Non-comparison Based Sorting methods.
Worst case time complexity of Bubble Sort is O (n2), where n indicates the number of elements to be sorted. It is applicable to small size data and usually is not used to solve problems in real-world applications. The best case and worst case time complexities of Insertion Sort are Ω (n) and O (n2) respectively. These are used in situations when the data to be sorted is small in size and is almost in a sorted order. The best case and worst case time complexities of Selection Sort are Ω (n2) and O (n2) respectively. These too are used when the data size is small. The space complexity of all the above sorting methods is equal to O (1), as these methods don’t require additional memory to get sorted order data. One can choose the above sorting methods when memory requirement is very high.
Merge Sort, Quick Sort, and Heap Sort are efficient sorting methods wherein time complexity is less. Among these sorting methods, Quick Sort is the fastest sorting method but its worst case time complexity is O (n2). Merge Sort and Heap Sort give O (nlogn) time complexity in all cases, i.e., best case, average case, and worst case. Quick Sort is preferred over Merge and Heap Sort if the researcher or developer is confident about balanced partitioning of the data.
Merge Sort is applicable in situations, when data size is very large and is unable to fit in a computer’s main memory like RAM although its space complexity is O (n). If there is a high requirement of memory and one wants to find the smallest or the largest element quickly, Heap Sort is preferred because its space complexity is O (1).
Radix Sort or Bucket Sort is specially used to sort out fixed size integers, fixed size strings and floating points of certain range and leads to worst case time complexity of O (d*(n+b)), where d is number of digits required to represent maximum number from the list, n indicates number of elements to be sorted and b indicates number of buckets required to sort out elements. For integers b=10, as there are 10 digits and for strings b=26, as there are 26 alphabets.
Counting Sort is one of the non-comparison based sorting methods, which runs in linear time, i.e., O (n+k), where n shows number of elements to be sorted and k is the maximum element. It is used when the range of the values is small and the list contains duplicate entries of the elements.
The author of this article is Prof. Ajitkumar Shtole with the Department of Computer Engineering at
International Institute of Information Technology, I²IT, Pune
Worst case time complexity of Bubble Sort is O (n2), where n indicates the number of elements to be sorted. It is applicable to small size data and usually is not used to solve problems in real-world applications. The best case and worst case time complexities of Insertion Sort are Ω (n) and O (n2) respectively. These are used in situations when the data to be sorted is small in size and is almost in a sorted order. The best case and worst case time complexities of Selection Sort are Ω (n2) and O (n2) respectively. These too are used when the data size is small. The space complexity of all the above sorting methods is equal to O (1), as these methods don’t require additional memory to get sorted order data. One can choose the above sorting methods when memory requirement is very high.
Merge Sort, Quick Sort, and Heap Sort are efficient sorting methods wherein time complexity is less. Among these sorting methods, Quick Sort is the fastest sorting method but its worst case time complexity is O (n2). Merge Sort and Heap Sort give O (nlogn) time complexity in all cases, i.e., best case, average case, and worst case. Quick Sort is preferred over Merge and Heap Sort if the researcher or developer is confident about balanced partitioning of the data.
Merge Sort is applicable in situations, when data size is very large and is unable to fit in a computer’s main memory like RAM although its space complexity is O (n). If there is a high requirement of memory and one wants to find the smallest or the largest element quickly, Heap Sort is preferred because its space complexity is O (1).
Radix Sort or Bucket Sort is specially used to sort out fixed size integers, fixed size strings and floating points of certain range and leads to worst case time complexity of O (d*(n+b)), where d is number of digits required to represent maximum number from the list, n indicates number of elements to be sorted and b indicates number of buckets required to sort out elements. For integers b=10, as there are 10 digits and for strings b=26, as there are 26 alphabets.
Counting Sort is one of the non-comparison based sorting methods, which runs in linear time, i.e., O (n+k), where n shows number of elements to be sorted and k is the maximum element. It is used when the range of the values is small and the list contains duplicate entries of the elements.
The author of this article is Prof. Ajitkumar Shtole with the Department of Computer Engineering at
International Institute of Information Technology, I²IT, Pune
Introduce Yourself (Example Post)
This is an example post, originally published as part of Blogging University. Enroll in one of our ten programs, and start your blog right.
You’re going to publish a post today. Don’t worry about how your blog looks. Don’t worry if you haven’t given it a name yet, or you’re feeling overwhelmed. Just click the “New Post” button, and tell us why you’re here.
Why do this?
- Because it gives new readers context. What are you about? Why should they read your blog?
- Because it will help you focus you own ideas about your blog and what you’d like to do with it.
The post can be short or long, a personal intro to your life or a bloggy mission statement, a manifesto for the future or a simple outline of your the types of things you hope to publish.
To help you get started, here are a few questions:
- Why are you blogging publicly, rather than keeping a personal journal?
- What topics do you think you’ll write about?
- Who would you love to connect with via your blog?
- If you blog successfully throughout the next year, what would you hope to have accomplished?
You’re not locked into any of this; one of the wonderful things about blogs is how they constantly evolve as we learn, grow, and interact with one another — but it’s good to know where and why you started, and articulating your goals may just give you a few other post ideas.
Can’t think how to get started? Just write the first thing that pops into your head. Anne Lamott, author of a book on writing we love, says that you need to give yourself permission to write a “crappy first draft”. Anne makes a great point — just start writing, and worry about editing it later.
When you’re ready to publish, give your post three to five tags that describe your blog’s focus — writing, photography, fiction, parenting, food, cars, movies, sports, whatever. These tags will help others who care about your topics find you in the Reader. Make sure one of the tags is “zerotohero,” so other new bloggers can find you, too.
