• About WordPress
    • WordPress.org
    • Documentation
    • Support
    • Feedback
  • Log In
  • Register
  • Home
  • Courses
  • Past Paper
  • FYP
  • Interview Questions
  • University Events
  • Contact
  • Quiz & Assignment
Cuitutorial
  • Home
  • Courses
  • Past Paper
  • FYP
  • Interview Questions
  • University Events
  • Contact
  • Quiz & Assignment

Data Structure

Home » Blog » Sorting and searching in data structure

Sorting and searching in data structure

  • Posted by saqib
  • Categories Data Structure
  • Date December 6, 2022
  • Comments 0 comment

What is Sorting?

Sorting is the process of ordering a list of objects, according to some linear order, such as £ for numbers.

Sorting can be divided into two types i.e. internal and external.

Internal sorting takes place in main memory of the computer, where we can make use of its random access nature.

External sorting is necessary when the number of objects to be sorted is too large to fit in the main memory.

For external sorting, the bottleneck is usually the data movement between the secondary storage and the main memory.

Data movement is efficient if it is moved in the form of large blocks.

However, moving large blocks of data is efficient only if it is physically located in contiguous locations.

The simplest algorithms usually take O(n2) time to sort n objects, and suited for sorting short lists.

Insertion sort takes O(n2) but if the input is pre-sorted running time takes O(N) time.

One of the most popular algorithms is Quick-Sort takes O(nlogn) time on average.

Quick-Sort works for most common applications, although in worst case it can take time O(n2) .

There are other sorting techniques, such as Merge-Sort that take time O(nlogn) in worst case.

Merge-Sort however, is well suited for external sorting.

  • sorted sub files are combined into a single larger file!

There are other algorithms such as “bucket” and “radix” sort when the keys are integers of known range. They take time O(n).

Sorting Techniques
Sorting Techniques

The sorting problem is to arrange a sequence of records so that the values of their key fields form a ascending/descending sequence.

The records may NOT have distinct values, and can appear in any order.

There are many criterion to evaluate the running time, as follows:

  • Number of algorithm steps.
  • Number comparisons between the keys (for expensive comparisons).
  • The number of times a record is moved (for large records).

 

Related links 

Single link list                 Stack              AVL Trees             Binary search          Counting Sort

Doubly link list               Queue              Graphs                  Bubble Sort               Radix sort

Circular link list              Binary search tree       Hashing         Insertion Sort         Bucket Sort

Josephus Problem          Tree Traversal              Heaps                Quick Sort              Merge Sort

 

At Cui tutorial, courses, past papers and final year projects

#tutorial #cui #pastpaper #courses #Finalyearproject

 

  • Share:
author avatar
saqib

Previous post

AVL Trees
December 6, 2022

Next post

Bubble Sort using C++
December 6, 2022

You may also like

Counting Sort
6 December, 2022

Counting sort is a type of Linear Time Sort Counting Sort was invented by H.H.Seward in 1954 All the sorting algorithms introduced so far share an                              …

Insertion Sort
6 December, 2022

Insertion Sort using loop and recursive function complete code On the ith pass we “insert” the ith element A[i] into its rightful place among A[1],A[2],…A[i-1] which were placed in sorted order. After this insertion A[1],A[2],…A[i] are in sorted order. Time …

Bubble Sort using C++
6 December, 2022

Bubble sort using loop and bubble sort in link list One of the simplest sorting methods. The basic idea is to move required value (smallest or highest ) to the top. Compare adjacent values (all elements) Swap values if required …

Leave A Reply Cancel reply

You must be logged in to post a comment.

admin@cuitutorial.com
Facebook-f Twitter Youtube Linkedin Instagram Stack-overflow Pinterest Github Quora Whatsapp
Courses
  • All Courses
  • Past Paper
  • Final year projects
  • Interview Questions
  • Contact
Important Pages
  • Privacy Policy
  • Terms of Service
  • Cookie Policy
Links
  • University Events
  • Team
Education & learning platform for All Computer science subjects
Final year projects
Past Paper
Interview questions
Programming, C/C++, Asp.net/MVC. Android, MySql, Jquery, Ajax, javascript, Php, Html5, Bootstrap4.
NTS, GAT, PPSC, FPSC

Copyright © 2021 | Cuitutorial